time-complexity - 查找以下代码的运行时间

Question

public static int loop(int n){
  int j = 1;
  int n2 = n;
  for (int i = 0; i < n; i++) {
    n2 *= 5.0/7.0;
      for (int k = 0; k < n2; k++) {
        System.out.println("Hello.");
      }
    }
  return j;
}

大家好，我在弄清楚上述代码的时间复杂度时遇到了一些困难。

这是我到目前为止所拥有的：

当 i=0 时，执行内循环：(5/7) * n

当 i=1 时，执行内循环：(5/7)^2 * n

...

当 i=n 时，执行内循环：(5/7)^(n+1) * n

总结它们，我得到 O(n * (5/7)^n)。这是一个准确的分析吗？

标签： time-complexitycomplexity-theory

Answer 1

你的结论不正确；事实上，当 0 < r < 1 时，公式 n * r ⁿ收敛到 0，因为 n 趋于无穷大，所以它绝对不是做超过 0 件事的算法运行时间的上限。

在您的算法中，r = 5/7，但为了便于阅读，我将在此答案中继续写 r。对这些项求和的公式给出的结果类似于 n * r * (r ⁿ⁺¹  - 1)/(r - 1)。r 的额外因子是因为序列不是从 1 * n 开始的。我们需要小心地简化这个公式，因为对于 0 < r < 1，分数的分子和分母都是负数，并且分子中的主导项是 1，它支配 r ⁿ⁺¹因为后者收敛到 0 为n 趋于无穷大。

如果我们将其重写为 n * r * (1 - r ⁿ⁺¹ )/(1 - r) 则更清晰。丢弃r 和 1/(1-r) 的常数因子我们得到 O(n * (1 - r ⁿ⁺¹ ))，然后丢弃支配项 -r ⁿ⁺¹我们得到 O(n * 1)，或者只是 O(n)。

另一种看待这一点的方式是，该序列以 n * (r + r ²  + r ³  + ...) 为界，其中无限级数收敛到常数 r/(1 - r)，因此它的边界为n 乘以一个常数。