O Notation beweise/wiederlege < Algorithmen < Schule < Informatik < Vorhilfe
|
| Aufgabe | Beweise oder wiederlege:
a) [mm] k^{n} [/mm] = [mm] O(l^{n}) [/mm] Konstanten k,l > 0 und k > l
b) [mm] O(6^{n}) [/mm] = [mm] 5^{O(n)} [/mm] |
Hallo,
irgendwie stehe fehlt mir ein Ansatz wie ich diese Bsp lösen könnte. Meine Ideen wären folgende gewesen.
a)
[mm] \limes_{n\rightarrow\infty} [/mm] f(n)/g(n) < [mm] \infty
[/mm]
[mm] \limes_{n\rightarrow\infty} k^{n}/l^{n} [/mm] < [mm] \infty
[/mm]
und da k > l würde ich sagen ist das [mm] k^{n} [/mm] viel schneller wächst als [mm] l^{n} [/mm] und darum das ergebnis [mm] \infty [/mm] ist. Ein c bzw. ein [mm] n_{0} [/mm] habe ich dazu aber auch noch nicht gefunden.
b)
[mm] O(6^{n}) [/mm] = [mm] 5^{O(n)}
[/mm]
da [mm] O(6^{n}) [/mm] irgend eine Funktion f(n) 'darstellt' kann man ja
f(n) = [mm] 5^{O(n)} [/mm] schreiben, allerdings weiß ich hier nicht mehr weiter wie ich zeigen soll, dass [mm] 5^{O(n)} [/mm] f(n) beschränkt.
bin über alle Tipps dankbar
lg tom
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 Fr 24.10.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
