c - 函数的运行时间

Question

令函数 f() 为:

void f(int n)
{
   for (int i=1; i<=n; i++)
     for (int j=1; j<=n*n/i; j+=i)
       printf(“*”);
}

根据我的计算，Big O 方法的运行时间应该是 O(n²log n)。
答案是 O(n²)。这是为什么？

Answer 1

我欠你一个道歉。我第一次看错了你的代码，所以我最初给出的答案是不正确的。这是一个更正的答案，以及与原始答案的比较，解释了我的分析哪里出了问题。我希望您觉得这很有趣 - 我认为由此产生了一些非常酷的数学!

您发布的代码显示在此处:

for (int i=1; i<=n; i++)
  for (int j=1; j<=n*n/i; j+=i)
     printf(“*”);

为了确定这段代码的运行时间，让我们看看内部循环在所有迭代中做了多少工作。当 i = 1 时，循环计数到 n² 个，因此它执行 n² 工作。当 i = 2 时，循环计数到 n²/2，因此它执行 n²/4。当 i = 3 时，循环以三为单位计数到 n²/3，因此它执行 n²/9。更一般地，第 k 次迭代执行 n²/k² 工作，因为它以大小为 k 的步长计数到 n²/k。

如果我们总结这里为 i 从 1 到 n(含)所做的工作，我们看到运行时是

n² + n² / 4 + n² / 9 + n² / 16 + ... + n² / n²

= n² (1 + 1/4 + 1/9 + 1/16 + 1/25 + ... + 1/n²).

此处的总和 (1 + 1/4 + 1/9 + 1/16 + ...) 具有(令人惊讶的!)属性，在极限情况下，it's exactly equal to π² / 6.换句话说，您的代码的运行时间渐近地接近 n² π/6，因此运行时间为 O(n²)。您可以通过编写一个程序将实际步数与 n² π/6 进行比较并查看结果来了解这一点。

我第一次弄错了，因为我误读了你的代码，就好像它是这样写的一样

for (int i=1; i<=n; i++)
  for (int j=1; j<=n*n/i; j+=1)
     printf(“*”);

换句话说，我认为内部循环在每次迭代中采用大小为 1 的步长，而不是大小为 i 的步长。在那种情况下，循环的第 k 次迭代完成的工作是 n²/k，而不是 n²/k²，这运行时间为

n² + n²/2 + n²/3 + n²/4 + ...n²/n

= n²(1 + 1/2 + 1/3 + 1/4 + ... + 1/n)

在这里，我们可以利用 1 + 1/2 + 1/3 + ... + 1/n 是众所周知的求和这一事实。第 n 个 harmonic number定义为 H_n = 1 + 1/2 + 1/3 + ... + 1/n 并且已知谐波数服从 H_n = Θ( log n)，所以这个版本的代码运行时间为 O(n² log n)。有趣的是，这种变化如此显着地改变了代码的运行时间!

作为一个有趣的概括，让我们假设您更改内部循环，以便步长为 i^ε 对于某些 ε > 0(并假设您四舍五入)。在这种情况下，第 k 次通过内部循环的迭代次数将为 n²/k^{1 + ε}，因为循环的上限为 n< sup>2/k，你的步数为 k^ε。通过与我们之前看到的类似的分析，运行时将是

n² + n² / 2^1+ε + n² / 3^1+ε + n² / 3^1+ε + ... + n² / n^1+ε

= n²(1 + 1/2^1+ε + 1/3^1+ε + 1/4^1+ε + ... + 1/n^1+ε)

如果你上过微积分类(class)，你可能会认识到这个系列

1 + 1/2^1+ε + 1/3^1+ε + 1/4^1+ε + ... + 1/n^1+ε

收敛到任何 ε > 0 的某个固定限制，这意味着如果步长是 i 的任何正幂，则总运行时间将为 O(n² ).这意味着以下所有代码片段的运行时间为 O(n²):

for (int i=1; i<=n; i++)
  for (int j=1; j<=n*n/i; j+=i)
     printf(“*”);

for (int i=1; i<=n; i++)
  for (int j=1; j<=n*n/i; j+=i*i)
     printf(“*”);

for (int i=1; i<=n; i++)
  for (int j=1; j<=n*n/i; j+=i*(sqrt(i) + 1))
     printf(“*”);