什么是快速逆转的时间复杂性？

Question

我看过apple开发者文档:

Array.reverse()

Array.reversed()

第一篇文章指出:复杂性:O(n),其中n是集合中元素的数量.

第二篇文章指出:复杂性:O(1),没有任何理由.

这只是一个小错误还是其他原因？

因为第二篇文章举了一个例子

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

我认为O(n)是正确答案.对？

Answer 1

这两种方法之间至关重要.reverse()变异Array到位,所以它的时间复杂性必须是O(n)因为它需要交换所有元素的顺序.

但是,另一方面,如果检查返回类型reversed(),那么ReversedCollection<Array<Element>>文档清楚地指出Array,该reversed()方法不是返回一个新实例,而是返回一个包装类型,它只包含原始数组,并提供对其元素的反向访问订购.这种包装类型ReversedCollection可以在恒定时间内创建,因此时间复杂度reversed()为O(1).

您提到的示例代码显然具有O(n)时间复杂性,因为word.reversed()使用循环遍历,但是,文档中提到的时间复杂度仅涉及函数调用word.reversed(),这实际上O(1)是出于上述原因.