问题：
如何找到具有内循环的算法的最坏情况时间复杂度？[副本]
楚举
int sum = 0;
for (int i = 1; i < N; i *= 2)
for(int j = 0; j < i; j++)
sum++;
我如何找到这段代码最坏情况下的时间复杂度？我看过许多关于发现时间复杂性的教程，我理解它们。但这一个似乎有点不同于教程中的那些。
共有1个答案
宇文念
让我们做简单的数学。每次迭代中i的值为1、2、4、8...（记录N+1个）术语。在每次迭代中，内循环执行I次。将i的值相加
T(N)=1+2+...+(logn+1)项，即具有a=1和r=2和N=(logn+1)的GP
T(N)=A[(RN-1)/(r-1)]
=1[(2(logn+1)-1)/(2-1)]
=2n-1
=O(N)
类似资料：
-
我已经浏览了Google和Stack Overflow搜索，但是我没有找到一个关于如何计算时间复杂度的清晰而直接的解释 对于下面这样简单的代码： 比如下面这样的循环： 这将只执行一次。时间实际上计算为而不是声明。
-
我已经阅读了这么多的资源，但仍然无法理解什么是时间复杂性。我阅读的参考资料基于各种公式，我理解用于表示时间复杂性，但我不知道如何表示。谁能请解释这个原则，以一个可以理解的明确的方式请给我。
-
null
-
我在计算时间复杂度时遇到困难，尤其是while循环： 示例1： 时间复杂度是O（n x 3 x r）还是O（3）？ 示例 2： 时间复杂度会是O(3 x n)还是O(3)？