Zeitkomplexität: O (logN) oder O (N)?

Question

Ich dachte, die Zeit Komplexität des folgenden Codes ist O (log N), aber die Antwort sagt, es ist O(N). Ich frage mich, warum:

int count = 0; 
for (int i = N; i > 0; i /= 2) { 
    for (int j = 0; j < i; j++) { 
     count += 1; 
    } 
} 

Für die inners for-Schleife, läuft es für diese oft: N + N/2 + N/4 ...

es scheint logN mir zu sein. Bitte hilf mir, warum hier zu verstehen. Danke

Answer 1

1, 1/2, 1/4, 1/8 ... 1/2 ** n ist eine geometrische Sequenz mit a = 1, r = 1/2 (a ist der erste Term und r ist das gemeinsame Verhältnis).

ihre Summe kann mit folgenden Formel berechnet werden:

In diesem Fall wird die Grenze der Summe gleich 2 ist, so:

n + n/2 + n/4 ... = n(1 + 1/2 + 1/4...) -> n * 2 

So ist die Mittäterschaft O (N)

Answer 2

Schritt für Schritt, basierend auf dem Code-Fragment, erhalten wir: