x <--1
for i <--0 to n do
k <-- i
while k> 0 do
x <-- x*2
k <-- k-1
return x
是O(n)吗? while 循环会增加复杂度吗?
最佳答案
当i = 0
时,内循环运行0
次
当i = 1
时,内部循环运行1
次
当 i = 2
时,内部循环运行 2
次
当 i = 3
时,内部循环运行 3
次
...
当i = n
时,内部循环运行n
次
全部加起来:0+1+2+3+...+n = n*(n+1)/2
所以时间复杂度是O(n^2)
关于algorithm - 该伪代码的大 O 是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55692444/