algorithm - 如何找到具有内部循环的算法的最坏情况时间复杂度？

<分区>

假设我有一个包含两个 for 循环的代码:

int sum = 0;
for (int i = 1; i < N; i *= 2)
   for(int j = 0; j < i; j++)
      sum++;

我如何找到这段代码的最坏情况下的时间复杂度？我看过很多关于寻找时间复杂度的教程，我理解了它们。但这一个似乎与教程中的那些有点不同。

最佳答案

让我们做简单的数学运算。每次迭代中 i 的值变为 1,2,4,8... (log N + 1) 项。在每次迭代中，内部循环进行 i 次。将 i

的值相加

T(N) = 1 + 2 + ... + (log N + 1) 项，即 GP with a = 1 and r = 2 and n = (log N + 1)

T(N) = a[(rⁿ-1)/(r-1)]
= 1[(2^(logN+1) - 1)/(2-1)]
= 2N - 1
= O(N)

所以在所有场景下复杂度都是O(N)。

关于algorithm - 如何找到具有内部循环的算法的最坏情况时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46081772/

相关文章：

algorithm - 从线性同余 RNG 生成随机向量