algorithm - 算法分析：大 O/最坏情况

Question

一个家庭作业问题要求我分析以下代码片段：

for (int i = N; i > 0; i--)
    for (int j = 0; j < i; j++)

我认为内部循环运行以下次数：

N + (N-1) + (N-2) + ... + (N - N + 1)

但是，我无法将其转换为 O() 表示法。

有人能指出我正确的方向吗？

Answer 1

通过观察，内部循环运行了 1 + 2 + ... + N 次。那正是 N(N+1)/2 （这是三角数的公式）。首先，记住 big-O 的定义：如果 |f/g| 则 f 是 O(g) 有足够大的 N 为界。例如，这是 O(exp(n))，也是 O(n^3)。也是 O(N(N+1)/2)，但你的老师可能期待 O(N^2) 的答案。如何证明这是 O(N^2)？那么 (N(N+1)/2) / N^2 是 1/2 + 1/2N。对于 N > 0，它以 1 为界。