Big-O:Warum ist die zeitliche Komplexität dieser Schleifen O(N)?
-
29-09-2020 - |
Frage
Ich habe folgende Funktion.
int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
Es hat O(N)
Zeitkomplexität.Ich dachte, das ist es O(N LogN)
(d. h.Wenn wir die innere Schleife entfernen, erhalten wir)
for (int i = n; i > 0; i /= 2){
...
}
Das ist O(Log N)
nicht wahr?Und es stellt sich heraus, dass es eine innere Schleife gibt O(N)
da es einfach linear ansteigt.Ich denke also, dass es so sein sollte O(Log N * N)
.Was könnte bei meinem Gedanken schiefgehen?
Lösung
Sehen Sie sich an, wie viele Schritte die innere Schleife ausführt.Es ist $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$.Allerdings die geometrische Reihe sagt uns:
$$\sum_{k=0}^{\lceil\log n ceil +c}\frac{n}{2^k} < n\sum_{k=0}^\infty \frac{1}{2 ^k} = 2n$$
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange