三重嵌套for循环的时间复杂度

Question

我正在努力找到确切的答案

for (int i=1; i<=n; i++)
   for (int j=i; j<=n; j++)
      for (int k=i; k<j; k++)
          sum++;

我知道外环运行了n次。然后，第二个循环每次运行的次数不同，因为它从i开始：

n（n-1）（n-2）。。。2 1.

但是，因为我们只关心最坏的情况（当i=n时），所以第二个循环将运行n-n次，因为它将从i=n开始。这当然没有意义，但这就是我被卡住的地方。我已经运行了这段代码，找到了序列的前四个元素：S=0 1 4 10。。。（其余部分不确定）。

抱歉，如果这不合理，但任何帮助将不胜感激！

Answer 1

重要的是要知道所有算术系列，如1 2 3... n都在O（n^2）中。因此，您会得到三个嵌套循环，每个都在O（n）中，因此总时间复杂度为O（n^3），或者更准确地说，θ（n^3）。

请注意，这里没有“最坏情况”或“最佳情况”，因为步数仅取决于n而不是其他。将其与例如排序算法进行比较，其中步数可能不仅取决于要排序的元素的数量n，还取决于元素的值及其特定顺序。