arrays - Swift Array reversed() 函数 O(1) 复杂度？

Question

我们可以使用 reversed 函数在 Swift 中反转数组，下面是示例:

let numbers = [3, 5, 7]
let reversedNumbers = Array(numbers.reversed())
print(reversedNumbers)
// Prints "[7, 5, 3]"

这是链接:Array reversed()

在讨论部分的最后，它说复杂度O(1)，我相信这是关于时间复杂度的，如何反转一个数组需要O(1)的时间？

Answer 1

实际上 reversed() 返回一个对原始数组进行包装的对象，而不是内容的实际反转，因此 O(1)。

如果您检查 reversed() 调用的返回类型，它是 ReversedCollection，它在内部将原始集合保留为 _base，除非其内容被修改.基本上 ReversedCollection 只是以相反的方式呈现/返回其基础集合的元素以节省时间和内存。

下面的例子表明，除非修改，否则反转数组与原始数组保持相同:

var originalArray = [1, 2, 3]
var reversedArray = originalArray.reversed()

print("0th index of OriginalArray \(originalArray[0])")
print("0th index of ReversedBaseArray \(reversedArray._base[0])")


print("0th index of OriginalArray \(originalArray.first)")
print("0th index of ReversedBaseArray \(reversedArray.first)")

originalArray[0] = 4 // Modification makes a separate copy of each instance
print("0th index of OriginalArray \(originalArray[1])")
print("0th index of ReversedBaseArray \(reversedArray._base[1])")


// Console Output:
// 0th index of OriginalArray 1
// 0th index of ReversedBaseArray 1


// First element of OriginalArray Optional(1)
// First element of ReversedBaseArray Optional(3)


// 0th index of OriginalArray 4
// 0th index of ReversedBaseArray 1