arrays - 快速逆转的时间复杂度是多少？

我读过苹果开发者文档：
Array.reverse()
Array.reversed()
第一篇文章指出：复杂性：O（n），其中n是集合中元素的数量。
第二篇文章指出：复杂性：O（1），没有任何理由。
这只是个小错误还是其他原因？
因为第二篇文章举了一个例子

let word = "Backwards"
for char in word.reversed() {
    print(char, terminator: "")
}
// Prints "sdrawkcaB"

我认为O（n）是正确的答案。正确的？

最佳答案

这两种方法之间有一个关键的重要性。reverse()使Array发生突变，因此它的时间复杂度必须是O(n)，因为它需要交换所有元素的顺序。
但是，另一方面，如果您检查reversed()的返回类型，则返回的是ReversedCollection<Array<Element>>，并且文档清楚地指出，Array方法返回的包装器类型不返回新的reversed()实例，而是简单地包含原始数组并按相反顺序提供对其元素的访问。这个包装类型，ReversedCollection可以在一定的时间内创建，因此reversed()的时间复杂性为O(1)。
您提到的示例代码显然具有O(n)时间复杂度，因为word.reversed()是使用循环遍历的，然而，文档中提到的时间复杂度仅涉及函数调用，word.reversed()，由于上面的原因，它确实是O(1)。