以下代码的增长顺序？

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。这是通过归纳为n（n + 1）（2n + 1）/ 6的1^2 + 2^2 + ... + n^2的大约四分之一。因此，增长的顺序是欧米茄（n^3）。

Answer 2

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

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

但是它仍然立方米。

Answer 3

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

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