Master Theorem Karatsuba < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:19 Mo 26.01.2009 | | Autor: | wap |
| Aufgabe | Bestimme eine Schranke vom Algorithmus KARATSUBA mit T(n) = 3 [mm] T(\frac{n}{2}) [/mm] + [mm] \theta(n)
[/mm]
|
Hallo, ich habe eine Frage zur Bestimmung einer Laufzeit mit Hilfe des Mastertheorems.
Ich würde gerne wissen wie ich bei dem Algorithmus Karatsuba, mit Hilfe des Mastertheorems schlussfolgern kann, welche Laufzeit ein Algorithmus hat. Ich habe mir dazu die Beispiele auf Wikipedia zu den 3 Fällen des Master Theorems bereits angeschaut und meine ich auch verstanden.
Jedoch kann ich bei einem Beispiel einen Schritt nicht ganz nachvollziehen.
Wir haben eine Gleichung gegeben mit
$ T(n) = 3 [mm] \cdot [/mm] T( [mm] \frac{n}{2} [/mm] ) + [mm] \theta(n) [/mm] $
Daraus können wir die Parameter $ a = 3 , b = 2$ und die Funktion $ f(n) = [mm] \theta(n) [/mm] $ schlussfolgern.
Im nächsten Schritt berechnen wir $ [mm] n^{Log_a(b)} [/mm] = [mm] n^{ Log_3(2) }$
[/mm]
Jetzt muss ich herausfinden in welchem Fall wir uns befinden. Dabei kennen wir die 3 hier:
Fall 1) $ f(n) = [mm] \mathcal{O}(n^{Log_a(b) - \epsilon}) [/mm] , mit [mm] \epsilon [/mm] > 0 $
Fall 2) $ f(n) = [mm] \mathcal{O}(n^{Log_a(b)}) [/mm] $
Fall 3) $ f(n) = [mm] \mathcal{O}(n^{Log_a(b) + \epsilon }), [/mm] mit [mm] \epsilon [/mm] > 0 $
Ich weiss bereits, dass es sich bei diesem Beispiel um Fall 1 handelt.
Also muss ich ein Epsilon so wählen, dass meine Funktion in $ [mm] \mathcal{O}(n^{Log_a(b) - \epsilon}) [/mm] $ liegt.
Jetzt würde ich gerne wissen, ob ich jetzt einfach "irgendein" $ [mm] \epsilon [/mm] $ wählen muss, welches groesser 0 ist?
Ich schaetze mal, man wählt im Regelfall $ [mm] \epsilon [/mm] = 1 $
Das würde heissen:
$ [mm] \theta(n) [/mm] = [mm] \mathcal{O}(n^{Log_3(2)- 1}) [/mm] $
Wie komme ich jetzt dahin, dass es Fall 1 ist?
Ich weiss dass $ [mm] \theta(n) [/mm] = [mm] \mathcal{O}(n) [/mm] = [mm] \Omega(n)$ [/mm] ist
müsste also den Limes bilden und zeigen, dass
$ [mm] \limes_{n\rightarrow\infty} [/mm] | [mm] \frac{ \theta(n) }{ \mathcal{O}(n^{Log_3(2)- 1}) } [/mm] | = c < [mm] \infty$
[/mm]
Nur hier weiss ich jetzt nicht wirklich weiter.
Im Endeffekt muss muss ich ja nur zeigen, dass meine Funktion $f(n)$ in [mm] $\mathcal{O}(n^{Log_3(2)- 1})$ [/mm] um schlussfolgern zu können, dass die Laufzeit
$ T(n) = [mm] \theta(n^{log_2(3)} [/mm] $ beträgt.
Wie macht ich das also?
Wäre dankbar für eine Antwort !
grüsse wap
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:22 Do 29.01.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
