大O记法——循环的疑惑

Question

最近我开始复习大O符号，遇到了一个很简单的问题。事实上，我有点困惑，如果有人能给我详细说明，那就太好了。

看下面的伪代码：

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²

Answer 2

谢谢。我正在读书，有两种不同的方法。第一个如下所述：

Boolean: ContainsDuplicates(Integer: array[])
    // Loop over all of the array's items.
    For i = 0 To <largest index>
        For j = 0 To <largest index>
        // See if these two items are duplicates.
        If (i != j) Then
            If (array[i] == array[j]) Then Return True
        End If
        Next j
    Next i

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

and then there is the other shared here as:

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

我猜这两个结果是一样的，即 N² 对吧？

大O记法——循环的疑惑

Big O notation - Doubts about the loop

algorithm

big-o

pseudocode