這個僞代碼的時間複雜度是多少？

Question

這是僞代碼。我試圖計算這個函數的時間複雜度，如this answer所說。它應該是這樣的：

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

也許時間複雜性是類似O(nlog(n))我猜？或者log(n)應該是log(n)基數3？有人說時間複雜度是O（n），這對我來說是完全不能接受的。

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

Answer 1

該算法將運行：

N + N/3 + N/9 + ... = series〜= O（3/2 * N）= O（N）

因爲3/2是常數。這裏第k個循環將以n/3步運行。

---

請注意從鏈接的問題，其中外環運行n倍的關鍵區別，並且是固定的。