Zeitaufwand des folgenden Algorithmus?

Question

Ich lerne jetzt Big-O-Notation und in diesem kleinen Algorithmus in einem anderen Thread gestolpert:

i = n 
while (i >= 1) 
{ 
    for j = 1 to i // NOTE: i instead of n here! 
    { 
     x = x + 1 
    } 
    i = i/2 
} 

an den Autor des Posts Nach ist die Komplexität Θ (n), aber ich kann nicht finde heraus, wie. Ich denke, die Komplexität der while-Schleife ist Θ (log (n)). Die Komplexität der for-Schleife aus dem, was ich dachte, wäre auch Θ (log (n)), weil die Anzahl der Iterationen jedes Mal halbiert würde.

Also, wäre die Komplexität des Ganzen nicht Θ (log (n) * log (n)), oder mache ich etwas falsch?

Edit: ist das Segment in der besten Antwort auf diese Frage: https://stackoverflow.com/questions/9556782/find-theta-notation-of-the-following-while-loop#=

Answer 1

Stellen Sie sich der Einfachheit halber n = 2^k vor. Wie oft wird x inkrementiert? Es folgt leicht Dies ist Geometric series

2^k + 2^(k - 1) + 2^(k - 2) + ... + 1 = 2^(k + 1) - 1 = 2 * n - 1

Also dieser Teil ist Θ(n). Auch i get's k = log n mal halbiert und es hat keine asymptotische Wirkung zu Θ(n).

Answer 2

Der Wert i für jede Iteration der while Schleife, die auch, wie viele Iterationen die for Schleife hat, sind n, n/2, n/4, ..., und die Gesamtkomplexität ist die Summe dieser. Das bedeutet ungefähr 2n, was dir dein Theta (n) bringt.