algorithm - 以下代码的增长顺序？

Question

我收到了以下问题，无法确定正确答案：

for (int i=1; i<=n/2; i++)
  for(int j=i; j<=n-i;j++)
    for(int k=i;k<=j;k++)
      x++;

x 作为 n 的函数的增长顺序是什么？

1. Ω(n^3)。
2. Θ(n^2.5)
3. Θ(n^2)
4. Ο(nlogn)
5. 以上都不是

我设法弄清楚：

T(n) = n*(n-1) + T(n-2)

但这并不能真正帮助我弄清楚增长的顺序。也许有更好的方法来找到它？

Answer 1

这看起来像一个家庭作业问题，所以我只会给你提示。

1）假设你只有内循环。作为 i 和 j 的函数，你经历了多少次内循环？循环的每次迭代执行多少次操作？总共应该执行多少操作？

2）现在假设你只有内部的两个循环。作为 i 和 n 的函数，你通过外循环多少次？每次经过外循环，您要经过多少次内循环？（提示：这应该根据 j 的不同而有所不同）总共应该执行多少操作？

3) 现在你已经准备好查看整个问题了。你经历了多少次内部的两个循环（作为 n 的函数），每次迭代应该执行多少操作？总共执行了多少次操作？（这是你的答案）

---

好吧，你说这不是作业问题，实际上它比我想象的要难，所以我就给你答案。

每个内部循环在时间 j - i 中运行。

第二个循环按时间运行 (i - i) + (i + 1 - i) + ... + (i + n - 2i - i) = 1 + 2 + ... + (n - 2i) = (n - 2i)(n - 2i + 1)/2，通过数学归纳法。

计算增长顺序时，1项相比n项非常小，所以外循环运行在大约n^2/2 + (n-2)^2/2 + (n-4)^2/2 + ... + 1/2。

这大约是 1^2 + 2^2 + ... + n^2 的四分之一，归纳起来是 n(n+1)(2n+1)/6。因此增长的顺序是Omega(n^3)。

Answer 2

有人在上面的评论中提到了打印语句。这里有一些：

n = 20 --> x = 715
n = 21 --> x = 825
n = 22 --> x = 946
n = 23 --> x = 1078
n = 24 --> x = 1222
n = 25 --> x = 1378
n = 26 --> x = 1547
n = 27 --> x = 1729
n = 28 --> x = 1925
n = 29 --> x = 2135
n = 30 --> x = 2360
n = 31 --> x = 2600
n = 32 --> x = 2856
n = 33 --> x = 3128
n = 34 --> x = 3417
n = 35 --> x = 3723
n = 36 --> x = 4047
n = 37 --> x = 4389
n = 38 --> x = 4750
n = 39 --> x = 5130
n = 40 --> x = 5530

Answer 3

我试图计算它，我发现T(n) = (13/12) * n * (n² + 3*n + 2)（数学规则！）。所以它是立方的。->回答 1。

编辑：计算中有错误。真正的答案是T(n) = n * (n + 2) * (2*n - 1) / 24：

但是它仍然是立方的。