---

Geschrieben von MIler am 28.03.2009 um 13:39:

  Komplexität

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 =)

---

Geschrieben von MIler am 28.03.2009 um 13:45:

 

[&#8730;n] soll wurzel (n) sein, keine Ahnung, warum er es nicht anzeigt