如何確定這個循環的時間複雜度？

Question

x=1; 
While(x<n) 
{ 
x=x + n/100; 
} 

我想弄清楚它是o（n）還是o（1）。因爲不管我們放在什麼地方，我認爲這個循環只會進行10次。

Answer 1

讓我們說n = 1.1 然後它會去10次，如果n = 1.2循環會繼續17次 如果n = 2它會繼續50次，當n> = 101循環會重複100次，即使N = 10^10000你還能找出

Answer 2

不幸的是你錯了它，它是O(n)或O(1)這是立即的事實清楚，它不可能是O(1)，因爲它需要對於不同的值n（甚至看n = 1,2,3,4,5）的迭代次數不同，並且它不能是O(n)，因爲它不會線性增長。

即使通過一些手動計算，你也可以清楚地看到它不會總是運行10次。檢查以下簡短的Python程序：

def t(n): 
    x = 1 
    c = 0 
    while x < n: 
     c += 1 
     x += n/100 
    return c 

a = [] 
for i in range(10000): 
    a += [i/100 + 1] 

with open("out.csv","w") as f: 
    for i in a: 
     f.write(str(i) + "," + str(t(i)) + "\n") 

使用Excel或其他應用程序，你可以很容易地走勢看下面的曲線中的迭代次數：

正是在這個不清楚指出所採用的迭代次數爲{0:100}範圍內的對數，其中n < 1取0次迭代，n > 100取100次。所以雖然Big-O符號不是我最好的主題，但我猜測時間複雜度是O(log(n))。