问题：
算法时间复杂度：在循环中I/=2
魏朗
int fun(int n) {
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
共有1个答案
解鸿运
外部循环将总共运行日志(n)次。现在，如果你观察内循环，它第一次运行n次，下一次运行n/2次，以此类推，这样就形成了级数
n(1 + 1/2 + 1/4 + 1/8 + 1/16 + ...)
它的和将是(2*n)，这意味着它是O(n)
因此，由于外循环运行O（logn）次，内循环运行O（n）次，所以时间复杂度为O（n）。
类似资料：
-
我很难理解算法分析，尤其是下面的例子： 所以我的理解是，外循环是，当我乘以一个常量时，我不确定是否有任何区别。 不过，最让我困惑的是内部循环。我认为它是，因为j被常数递减，但我不确定和
-
我在计算时间复杂度时遇到困难，尤其是while循环： 示例1： 时间复杂度是O（n x 3 x r）还是O（3）？ 示例 2： 时间复杂度会是O(3 x n)还是O(3)？
-
我的困惑是- 如果我把n+(n^2-1)*O(1)写成n+O(1)+O(1)+........+O(1)，那么我可以忽略低阶项，复杂性将是O(n)，但是另一个推理可以是一个常数的工作量正在做n^2次，所以时间复杂性应该是O(n^2) 在这个问题中也发生了类似的事情-带有if语句的嵌套循环的时间复杂度O(N):O(N^4)？
-
我在计算一个方法的时间复杂度： D总是小于或等于P，但我的怀疑是在后四个。我的时间复杂度是O(2p^3)，但我读过2可以像O(p^3)一样去掉。这些是正确的吗？
-
以下示例循环的时间复杂度为O（n^2），有人能解释为什么是O（n^2）吗？因为这取决于c的价值。。。 循环1--- 回路2--- 如果c=0；然后它运行无限次，就像增加c值一样，内部循环的运行次数也会减少 有人能给我解释一下吗？