algorithm - 计算代码的时间复杂度

Question

我有以下代码用于我的一个应用程序。我想计算这段代码的时间复杂度。

      for (int i = 0; i < n-1; i++)
        {
            for (int j   = 0; j < n-i-1; j++)
            {
                //TODO
            }
        }

我试过用下面的方法计算它：

: (n-1)(n-I-1)
: (n)(n-I-1) - (n-I-1)
: n^2-ni-n-n+i+1
: n^2-ni-2n+i+1

我不知道如何得出结论。虽然我看到 n 的最大值是 o(n^2)。任何人都可以建议确定时间复杂度的下一步是什么..

Answer 1

你快到了。下一步是从多项式中删除低阶项：-ni-2n+i+1剩下n^2.

通常，您还将删除附加到的任何乘法常数n^2。IE。加入得到5_5*n^2n^2

这是从 big-Oh 的定义得出的，它关心一个函数是否随着输入大小的增加而支配另一个函数。随着输入大小的增加，唯一重要的术语是n^2。低阶项不允许这个函数支配另一个函数，任何常数也不会。所以你把它们扔掉。

Answer 2

此代码片段与此相同：

for m in n-1..0
    for j in 0..m
      i = n-1-m
      ...

这是“经典” O(N^2)，除了外循环从高到低而不是从低到高。