该伪代码的大 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)