big-o - 什么是嵌套循环的 Big-O，其中内循环的迭代次数由外循环的当前迭代确定？

Question

以下嵌套循环的 Big-O 时间复杂度是多少:

for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
        System.out.println("i = " + i + " j = " + j);
    }
}

仍然是O(N^2)吗？

Answer 1

是的，它仍然是 O(n^2)，它有一个更小的常数因子，但这不会影响 O 表示法。