algorithm - 程序的时间复杂度

Question

我刚刚学习时间复杂度，这是我写的一段代码

for (int i = 1; i <= N; i++)
  for (int j = 1; j <= N; j++)
  {
    // Spread Peace
  }

很明显，上面的那个是 O(N^2) 复杂度并且它似乎(对于 N == 1e6)永远运行。

这是第二段代码

for (int i = 1; i <= N; i++)
  for (int j = i; j <= N; j++)
  {
    // Money is Everything
  }

上面的代码也是O(N^2) - N*(N+1)/2 复杂度也一直在运行，但是这段代码:

for (int i = 1; i <= N; i++)
  for (int j = i; j <= N; j += i)
  {
    // Be my GirlFriend
  }

只是在一秒钟内执行，我无法推导出它的时间复杂度为什么这么快？ N == 1e6 的估计是多少？

Answer 1

让我们先进行一个实验，让我们尝试展开循环(C# 实现)，看看发生了什么:

 private static IEnumerable<String> Unroll(int N) {
  for (int i = 1; i <= N; i++) {
    StringBuilder sb = new StringBuilder();

    for (int j = i; j <= N; j += i) {
      if (sb.Length > 0)
        sb.Append(", ");

      sb.Append(j);
    }

    yield return sb.ToString();
  }

小数字(例如 16)的测试运行揭示了图片

  Console.Write(string.Join(Environment.NewLine, Unroll(16)));

您能看到这种模式吗？呈指数下降？看起来像 N * log(N)，对吧？

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
2, 4, 6, 8, 10, 12, 14, 16
3, 6, 9, 12, 15
4, 8, 12, 16
5, 10, 15
6, 12
7, 14
8, 16
9
10
11
12
13
14
15
16

现在轮到纸笔了:我们有(对于大的 N)

   N / 1 items (step == 1) +
   N / 2 items (step == 2) +
   N / 3 items (step == 3) +
   ...
   N / N items (step == N)
------------------------------
   N * (1 + 1/2 + ... + 1/N) = 
   N * H(N) = 
   O(N * log(N)) // Harmonic sum H(N) gives log(N)  

更准确的估计

   H(N) = ln(N) + gamma + 1/(2*N) + ...

在哪里

   ln()  - natural logarithm
   gamma - Euler–Mascheroni constant (0.5772156649...)

为 N == 1e6 提供了关于 14.4e6 的循环，实际上，高估了；实际计数是 13970034 (14.0e6)，因为在用谐波级数近似时我们没有进行整数除法(每个 k/N 应该是整数，即不是k/N，而是floor(k/N))。