 Komplexität |
MIler
unregistriert
 |
|
Hallo zusammen,
ich habe ein kleineres Problem mit mehren Aufgaben. Unser Professor hat sie und nicht wirklich erklärt, wie man vorgehen muss, darum hoffe ich, dass ihr mir sie erklären könnt.
[u]Ich habe folgende Aufgabe:[/u]
[i]Gegeben seien folgende Funktionen f(n) und g(n):[/i]
[i]f(n) = [√n], f(n) = [log10(n)], f(n) = 176n2+24n+17[/i]
[i]g(n) = 1000n, g(n) = [log2(n)], g(n) = [√n], g(n) = [nlog22(n)], g(n) = n2, g(n) = n3[/i]
[i][/i]
[i]Geben Sie für jede Kombination von f und g an, ob f(n) = O(g(n)) gilt. Geben Sie zum Nachweis, dass f(n) = O(g(n)) gilt, eine entsprechende Ungleichung mit den zugehörigen Werten für k und n0 an (f(n) <= k*g(n), n >= n0).[/i]
[i]Hinweis: Für den Zehnerlogarithmus und eine beliebige Basis b gilt: log10(n) = log10(b) * logb(n)[/i]
Nur leider habe ich keine Ahnung, ich hoffe ihr könnt mir helfen.
Vielen Dank im vorraus =)
|
|
28.03.2009 13:39 |
|
|
MIler
unregistriert
|
|
[√n] soll wurzel (n) sein, keine Ahnung, warum er es nicht anzeigt
|
|
|
28.03.2009 13:45 |
|
|
|
