时间戳

首页 > 解决方案 > Swift'compactMap'Sequence 方法的时间复杂度

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

问题描述

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).

标签： swiftsequence

解决方案

该文档实际上并未说明这是算法的时间复杂度还是内存复杂度。

时间复杂度确实是，O(n)但是内存复杂度是O(n+m)，因为原来Sequence的 sizen保存在内存中，而新Array的 sizem也被创建了。

推荐阅读