時間複雜度 - 過度操作？

Question

當我只把它算作一個操作時，是否有可能完全超越了操作的複雜性？這是我從班上獲得的任務。

Algorithm Power(n) 
Pre: n :: Integer, n > 0 
i = 1 
while (i < n) 
    print i 
    i = i * 3 
done 

我完全不清楚自己的，認爲我過分思考的問題

簡化前的時間複雜度爲O（N）是O（N）= 1 +（3N +？+ 1 ） 每次循環完成i = i * 3的次數是每次循環一次，但變量「i」以每次迭代的加速速率增長這實際上很重要還是我過度考慮事情太多？

它是O（n），因爲它只是一個循環或者比它更復雜，而且由於「i」加速而沿着O（log n）或O（n ^（1/3））的線。

Answer 1

你是對的，它不是O(n)。僅當循環計數器（在此例中爲i）相對於n線性增加時，單級循環纔對應於O(n)。至於是O(log n)還是O(n^(1/3))，我會留給你看看，因爲這是作業。