Komplexität von Funktion bestimmen?
Das ist die Funktion. Leider gibts für die Aufgabe keine Lösung, aber ich hätte gesagt, dass die innere Schleife log_2(n) Höchstens log_2(n) Durchläufe hat, weil k ja immer mindestens halbiert wird. Zusammen mit der äußeren Schleife wäre das n * log n
Aber die äußere Schleife macht ja eigentlich nichts, wenn k = 0 ist. Muss das n dann trotzdem mitberechnet werden oder würde hier auch ein log n reichen, sodass es auf log^2 n rauslaufen würde?
Als Lösung muss x so gewählt werden (das kleinste x ist gesucht), dass der Algorithmus in O(n^x) ist.
Lässt sich n log n überhaupt so darstellen?
2 Antworten
Du weist n der Variable k zu. In dem Fall wäre k == n. Das passiert wo du sagst
int k = n;
Die äußere Schleife wird daher mit n Durchläufen durchlaufen, da du es ja übergibst. Weiter unten weißt du den Wert n k zu.
Die äußere Schleife wird 1 mal durchlaufen und die innere n Mal. Bevor er WIEDER in die äußere Schleife gesprungen wird, wird return aufgerufen und sum zurückgegeben.
die Äussere schleife und die innere werden jeweils n mal durch laufen
Aber k wird auch pro Durchlauf der äußeren Schleife halbiert. Ändert das nichts?
stimmt, das hab ich über sehen, dann stimmt für innen das log von dir
Und wo ist das k/2?