algorithm - 该伪代码的大 O 是什么?

标签 algorithm time-complexity big-o analysis pseudocode

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/

相关文章:

c++ - 使用平方根计算质数和算法构建查询

java - 检测字符串是否具有唯一字符 : comparing my solution to "Cracking the Coding Interview?"

algorithm - 嵌套算法的计算复杂度

algorithm - O(1), O(n), O(n*n) 内存是什么意思?

algorithm - 进行 k 选择的最坏情况 O(n) 算法

php - 数组排序和合并算法

Swift:分组配对,算法

c++ - 字符串中的 Rs 数

javascript - JavaScript 中 includes 方法的时间复杂度

python - 在 python 中获取子字符串是 O(n) 操作吗?