Komplexität |
| 28.03.2009, 13:39 | Auf diesen Beitrag antworten » |
| MIler | 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 =) |
|
|
|
| 28.03.2009, 13:45 | Auf diesen Beitrag antworten » |
| MIler | [√n] soll wurzel (n) sein, keine Ahnung, warum er es nicht anzeigt |
|
|
