Komplexitätsklasse berechen |
| 10.11.2013, 17:29 | Auf diesen Beitrag antworten » |
| otter | Komplexitätsklasse berechen Meine Frage: Gegeben sind die folgenden 8 Funktionen: a) Ta(n)= (n^2 + n)/(n-1) b) Tb(n)= log(3n^(n^2)) + n^2 c) ... usw. Berechnen Sie für jede Funktion Tx die jeweil kleinstmögliche Komplexitätsklasse O(f), so dass Tx element O(f), für eine Funktion f von n. Geben Sie die Komplexitätsklasse jeweils in einer der Formen O(c), O(n^c)... an (für eine jeweils entsprechende Konstante c). Meine Ideen: Ich habe überhaupt keine Ahnung wie ich solch eine kleinstmögliche Komplexitätsklasse berechnen soll, da das in der Vorlesung leider nicht gezeigt wurde. Mein Ansatz wäre anhand der Funktion eine Komplexitätsklasse zu raten. Für a) wäre das O(n^2) zB. Weiter mit 0 <= Ta(n) <= c* n^2 Ta(n) vereinfachen und dann daraus n und c schließen. Allerdings wüsste ich nicht wie ich Ta(n) vereinfachen soll. Ein Ansatz, den ich verstehe, würde mir völlig reichen 
LG otter |
|
|
|
|
|
