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

Question

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

然而，当看到标准库中的实现时，我无法理解为什么：

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)，然而，内存复杂性