ios - enumerated() 常数时间 O(1) 是如何实现的？

Question

我正在查看有关 Array 类型的 enumerated() 的文档，并注意到它说:

Complexity: O(1)

https://developer.apple.com/documentation/swift/array/1687832-enumerated

这似乎没有意义，因为遍历数组的时间是线性的 - O(n) - 因为数组的长度是未知的。 enumerated() 必须遍历数组才能返回 EnumeratedSequence。这个函数的常数时间复杂度如何？

Answer 1

创建一个 EnumeratedSequence 归结为 initializing它的迭代器。后者分两步完成:

• 有一个指向调用 enumerated() 的基础集合或序列的指针。
• 初始化内部变量_count为0

执行这两个步骤所花费的时间不会随着集合/序列中元素的数量而改变。

遍历 EnumeratedSequence 的元素等同于调用 .next()在 EnumeratedSequence 的迭代器上。它(按需)创建一个元组 let result = (offset: _count, element: b) 只要基本集合/序列中有元素(因此是 guard 语句)，并递增 _count += 1。

概括一下:创建一个枚举序列是 O(1)，但遍历所有元素当然是 O(n)。