swift - Swift 'compactMap' Sequence 方法的时间复杂度

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

文档实际上并没有说明这是否是 时间 或 内存复杂度的算法。
时间复杂度 是 O(n)然而，确实，内存复杂度是 O(n+m) ，自原Sequence尺寸n保存在内存中，而一个新的 Array尺寸m也被创建。