Laufzeitschranke < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Betrachten die folgende as. Gleichungen und zeigen Sie, welche korrekt sind; Beweisen Sie Ihre Aussagen:
8^(ld n) = Theta [mm] (n^3)
[/mm]
[mm] n^2 [/mm] = [mm] O(7^n)
[/mm]
[mm] 2^n [/mm] = [mm] Theta(3^n)
[/mm]
[mm] n^n [/mm] = Omega(n!) |
Kann man mit dementsprechenden Ansätzen die Gleichungen beweisen:
für [mm] \Omega [/mm] = f(n) = [mm] \Omega(g(n)) [/mm] <=> [mm] \exists [/mm] c [mm] \in [/mm] R, c > 0, n0 [mm] \in [/mm] N : f(n) [mm] \ge [/mm] c · g(n) [mm] \forall [/mm] n [mm] \ge [/mm] n0
für O = f(n) = O (g(n)) <=> [mm] \exists [/mm] c [mm] \in [/mm] R, c > 0, n0 [mm] \in [/mm] N : f(n) [mm] \le [/mm] c · g(n) [mm] \forall [/mm] n [mm] \ge [/mm] n0
für [mm] \Theta [/mm] = f(n) = [mm] \Theta(g(n)) [/mm] <=> [mm] \exists [/mm] c1, c2 [mm] \in [/mm] R, c1, c2 > 0, n0 [mm] \in [/mm] N : c1 · g(n) [mm] \le [/mm] f(n) [mm] \le [/mm] c2 · g(n)
Bzw. wie kommt man von 8^ld(n) auf [mm] n^3??
[/mm]
Oder kann man hier auch den limes ansetzen?
lg
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Fr 05.10.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
