Swift 'compactMap‘序列方法的时间复杂度

Question

Swift文档指出，用于排序的compactMap()方法的时间复杂度为O(n + m)，其中n是序列的长度，m是结果的长度。

但是，在查看标准库中的implementation时，我不明白为什么：

public func _compactMap<ElementOfResult>(
    _ transform: (Element) throws -> ElementOfResult?
  ) rethrows -> [ElementOfResult] {
    var result: [ElementOfResult] = []
    for element in self {
      if let newElement = try transform(element) {
        result.append(newElement)
      }
    }
    return result
  }

序列元素上只有一个循环，它应该是O(n)。

Answer 1

文档实际上并没有说明这是算法的time还是memory complexity。

时间复杂度实际上是O(n)，然而，存储器复杂度是O(n+m)，因为大小为n的原始代码被保存在存储器中，同时还创建了大小为< Array >d13Sequence >的新代码。