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

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/