exakte schranke < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:38 Di 27.10.2009 | | Autor: | den9ts |
| Aufgabe | Gegeben seien die folgenden Rekursionsgleichungen jeweils f¨ur eine Funktion T.
(a) T(n) = 9T(n/3) + [mm] 2n^2 [/mm] + n
(b) T(n) = T(n/2) + [mm] n^5 [/mm] + 1
(c) T(n) = 27T(n/3) + [mm] 100n^2 [/mm] + √n
(d) T(n) = nT(n − 1)
(e) T(n) = T(n/2) + [mm] log_2 [/mm] n
Bestimmen Sie jeweils eine exakte Schranke f¨ur das Verhalten von T. Finden Sie also eine
Funktion f, so daß T ∈ (f). In den F¨allen, wo die polynomiale Version des Master-Theorems
anwendbar ist, benutzen Sie dieses zum Finden von f und geben a, b und k an. |
sitz seit über ner halben stunde an der (a) und find dort kein anfang...
definition von einer exakten schranke hab ich hier.. und zwar ist das wenn eine funktion f eine obere und eine untere schranke von T(n) bildet.
sodass ich erstmal ein f(n) finden muss, sodass gilt 9T(n/3) + [mm] 2n^2 [/mm] + n [mm] \le [/mm] c*f(n)
außerdem soll 9T(n/3) + [mm] 2n^2 [/mm] + n * c [mm] \ge [/mm] f(n)
oder seh ich das falsch?
komm irgendwie auch 0 mit T(n/3) klar.. das muss doch in irgendeiner abhängigkeit zu T(n) stehen.. hab nur keinen blassen schimmer wie ich darauf komm, auch wenns wahrscheinlich total offensichtlich is
bräuchte auf jeden fall dringend nen schubs in die richtige richtung.. danke >.<
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Do 29.10.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
