swift - 是第一个(其中 :) Method always O(n) or it can be O(1) with usage of Set or Dictionary?

Question

我想知道如果我使用 Set 而不是 Array 可以我的方法 first(where:)复杂度:O(1)？
Apple 表示 first(where:)方法是 O(n)，一般是这样还是取决于我们如何使用它？
例如看看这两种编码方式:

var numbers: [Int] = [Int]()
numbers = [3, 7, 4, -2, 9, -6, 10, 1]

if let searchResult = numbers.first(where: { value in value == -2 })
{
    print("The number \(searchResult) Exist!")
}
else
{
    print("The number does not Exist!")
}

和这个:

var numbers: Set<Int> = Set<Int>()
numbers = [3, 7, 4, -2, 9, -6, 10, 1]

if let searchResult = numbers.first(where: { value in value == -2 })
{
    print("The number \(searchResult) Exist!")
}
else
{
    print("The number does not Exist!")
}

我们可以说第二种方式的复杂度是 O(1) 吗？

Answer 1

即使您使用 Set，它仍然是 O(n) . .first(where:)定义在一个序列上，需要一次检查序列中的项，找到第一个使谓词true的项。 .
您的示例只是检查项目是否存在于 Set 中，但由于您使用的是 .first(where:)和一个谓词 { value in value == -2} Swift 将依次为序列中的每个元素运行该谓词，直到找到返回 true 的元素为止。 . Swift 不知道您实际上只是在检查该项目是否在集合中。
如果你想要 O(1) ，然后使用 .contains(-2)在 Set .