如何确定这个循环的时间复杂度？

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))。