Zeitkomplexität für abhängige verschachtelte For-Schleife?

Question

Können Sie mir erklären, wie Sie die zeitliche Komplexität dafür finden?

sum=0; 
for(k=1;k<=n;k*=2) 
    for(j=1;j<=k;j++) 
    sum++; 

Also, ich weiß, die äußere Schleife Zeitkomplexität von O (log n), aber da die Iterationen der inneren Schleife auf dem Wert der äußeren Schleife hängt, ist die Komplexität dieses Algorithmus nicht O (nlogn).

Das Buch sagt, es ist O (n).

ich wirklich nicht verstehen, wie es O (n) ist ... Kann jemand bitte erklären ... werde ich wirklich dankbar, wenn u btw in die Details gehen könnte: D

Eine mathematische Lösung mir helfen, besser zu verstehen, würde ...

Answer 1

der äußeren Schleife ausgeführt log (Base2) n times.so ist O (log (Base2) n).

Die innere Schleife wird k mal für jede Iteration der äußeren Schleife ausgeführt. Jetzt wird k in jeder Iteration der äußeren Schleife auf k * 2 inkrementiert.

so Gesamtzahl der Iterationen der inneren Schleife = 1 + 2 + 4 + 8 + ... + 2^(log (Base2) n)
= 2^0 + 2^1 + 2^2 + .. . + 2^log (base2) n (geometric series)
= 2^((log (base2) n + 1) -1/(2-1)
= 2n-1.
= O (n)
so die innere Schleife ist O (n). Also gesamte Zeitkomplexität = O (n), wie O (n + log (base2) n) = O (n)

UPDATE: Es ist auch O (nlogn) weil nlogn >> n für großen Wert von n, aber es ist nicht asymptotisch fest, man kann sagen, es ist o (nlogn) [Small o].

Answer 2

nur sehen, wie oft die innere Schleife läuft:

1 + 2 + 4 + 8 + 16 +...+ n 

Beachten Sie, dass, wenn n = 32, dann ist dies sum = 31 + 32. ~ 2n.
Dies liegt daran, dass die Summe aller Begriffe außer dem letzten Begriff fast gleich dem letzten Begriff ist.

Daher die Gesamtkomplexität = O(n).

EDIT:

der geometrischen Reihe sum (http://www.mathsisfun.com/algebra/sequences-sums-geometric.html) in der Größenordnung ist von:

(2^(logn) - 1)/(2-1) = n-1. 

Answer 3

Ich glaube, Sie gehen sollen wie die folgenden formell Ihren Algorithmus, um Wachstum Komplexität zu erhalten, unter Verwendung von Mathematik (Sigma Notation):