java - Java 嵌套循环的大 O 表示法

Question

我知道 Big O 的各种速率，例如 O(n^2) 和 O(n)，并且可以毫无问题地确定简单嵌套 for 循环的 Big O 值，如下所示。

for (int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
   //Simple Statement

下面的循环显然是 O(n^2)，但是当内部嵌套循环依赖于外部循环时，如何求解大 O。 示例

for ( int i = 0; i < n; i++)
    for (int j = n - 1; j >= i; j--)
    //Simple Statement

T(n) 会是 n*(n-1-i) 吗？

在此先感谢您的帮助!

Answer 1

还是n^2阶。您只关心最重要的术语。第二个表达式看起来像是 O(n^2 - an) 行，其中 a 是某种系数。您真正关心的是 n^2。