Wie groß ist die zeitliche Komplexität dieses Pseudocodes?

Question

Dies ist Pseudocode. Ich habe versucht, die Zeitkomplexität dieser Funktion zu berechnen, wie this answer sagte. Es sollte wie sein:

n + n/3 + n/9 + ... 

Vielleicht ist die Zeit Komplexität so etwas wie O(nlog(n)) ist, ich denke? Oder die log(n) sollte log(n)base 3 sein? Jemand sagte, die Zeitkomplexität sei O (n), was für mich völlig inakzeptabel ist.

j = n 
while j >= 1 { 
    for i = 1 to j { 
     x += 1 
    } 
    j /= 3 
} 

Answer 1

Der Algorithmus läuft in:

n + n/3 + n/9 + ... = series ~ = O (3/2 * n) = O (n)

seit 3/2 ist eine Konstante. Hier läuft die k-te Schleife in n/3 ^k Schritten.

---

Bitte beachten Sie den entscheidenden Unterschied aus der verknüpften Frage, wo die äußere Schleife n mal läuft und dass festgelegt ist.