时间戳

首页 > 解决方案 > 大 O 表示法 - 对循环的怀疑

algorithm - 大 O 表示法 - 对循环的怀疑

问题描述

最近我开始复习 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：

对于 j = i + 1 到 N

谢谢

标签： algorithmbig-opseudocode

解决方案

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

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

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

在大 O 表示法中，这相当于 N²

推荐阅读