那个伪代码的大O是什么？

Question

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循环会增加复杂性吗？

Answer 1

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

Answer 2

我同意上面的xashru。为O（n ^ 2）