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# 实现)，看看发生了什么: p>

 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))。