Swift 数组 reversed() 函数复杂度为 O(1)？

Question

我们可以使用 reversed 函数反转 Swift 中的数组，示例如下：

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

这是 link :Array reversed()

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

Answer 1

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

如果您检查 reversed() 调用的 return 类型，它是 ReversedCollection，它在内部将原始集合保留为 _base，除非其内容被修改。基本上 ReversedCollection 只是其基础集合的 presenting/returning 个元素以相反的方式保存 time 和 memory.

以下示例显示反转数组与原始数组保持相同，除非它被修改：

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

Swift 数组 reversed() 函数复杂度为 O(1)？

Swift Array reversed() function O(1) complexity?

arrays

reverse

swift