asymptotische Komplexität < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:47 Di 19.09.2006 | | Autor: | G3kkoo |
| Aufgabe | Bestimmen Sie die asymptotische Komplexität der Funktion:
[mm] g(n)=5n^{3}+7n+10 log_{5}(n) [/mm] |
Halli Hallo,
das ist eine Klausuraufgabe und ich weiß nicht ob die Antwort Logarithmisch ist oder Kubisch.. Ich hoffe das nichts anderes gefragt ist..
Danke schön
|
|
| |
|
Hallo und guten Morgen,
sicher hattet Ihr doch den Begriff der asymptotischen Komplexität irgendwo mal definiert bekommen, oder ?
Wäre hilfreich, das noch nachzureichen.
Sicherlich gilt [mm] g(n)=\Theta (n^3), [/mm] d.h. es gibt Konstanten [mm] 0<\:c \: [/mm] <C und ein [mm] n_0\in\IN, [/mm] so dass für alle [mm] n\geq n_0
[/mm]
[mm] c\cdot n^3\:\leq g(n)\leq C\cdot n^3.
[/mm]
Es gilt sogar
[mm] \lim_{n\to\infty} \frac{|g(n)-5\cdot n^3|}{5n^3}=0, [/mm] oder anders:
[mm] g(n)=5n^3+h(n) [/mm] mit [mm] h(n)=7n+10\log_5(n)=o(n^3).
[/mm]
Gruss,
Mathias
|
|
|
|
