algorithm - 大O记法——循环的疑惑

Question

最近我开始复习 Big O notation 并遇到一个非常简单的问题。事实上，我有点困惑，如果有人能给我提供详细信息，那就太好了。

看下面的伪代码:

Boolean: ContainsDuplicates(Integer: array[])
    // Loop over all of the array's items except the last one.
    For i = 0 To <largest index> - 1
        // Loop over the items after item i.
        For j = i + 1 To <largest index> N
            // See if these two items are duplicates.
            If (array[i] == array[j]) Then Return True
        Next j
    Next i

    // If we get to this point, there are no duplicates.
    Return False
End ContainsDuplicates

我想知道哪个大 O 代表下面的循环，因为 j 的初始值是 i + 1:

For j = i + 1 To N

谢谢

Answer 1

• 第一个循环:1 到 N
• 第二个循环:2 到 N
• 第三个循环:3 到 N...
• 在最后一个循环之前:N-2 到 N
• 最后一个循环:N-1到N

你看到什么规律了吗？这就像做 1+2+3+...+(N-1)+N

实现这个的公式是 (N+1)(N)/2

在大 O 表示法中，这等同于 N²