在 Swift 3.0 中访问带有索引的字符串的大 O

Question

什么是访问的复杂性String与index在swift3.0吗？

复杂性是否与数组访问或 O(N) 或其他东西相同？

从“字符串索引”下的文档中：

let greeting = "Guten Tag!"
let index = greeting.index(greeting.startIndex, offsetBy: 7)
greeting[index]
.
.
.
for index in greeting.characters.indices {
    print("\(greeting[index]) ", terminator: "")
}
// Prints "G u t e n   T a g ! "

如果索引访问是 O(N)，那么最后一个示例（遍历字符）将非常糟糕，因为仅以这种方式遍历字符将是 O(n^2)

我不确定的原因是以下声明：“不同的字符 [...] 可能需要不同数量的内存来存储”。

如果复杂度不是 O(n)，那么它是如何工作的，因为不能只是将偏移量乘以常数来获得内存中的字符？

Answer 1

除非另有说明，Collection的subscript要求的实现应始终具有 O(1) 时间复杂度。它是与Collection自身契约的一部分。

正如文档所述（强调我的）：

符合 的类型Collection应提供start?Index和end?Index属性和对元素的下标访问作为 O(1) 操作。不能保证预期性能的类型必须记录离开 [...]

当您推进索引（例如使用index(_:offsetBy:). 对于 a RandomAccessCollection，此操作的复杂度为 O(1) ，否则为O(n)，其中 n 是偏移量的大小。

String.CharacterView不是 a RandomAccessCollection，因此推进索引是 O(n)。正如您所说，这样做的原因是字符可以具有不同的字节长度。但是一旦你有了索引（它在内部只是字符串的 unicode 标量的偏移值以及 UTF-16 代码单元中给定的扩展字素簇的长度），你就可以在恒定时间内下标。

所以

for index in greeting.characters.indices {
    print("\(greeting[index]) ", terminator: "")
}

是 O(n)。循环的每次迭代只是将当前索引向前推进 1，下标使用索引的偏移量跳转到扩展字素簇的开头，从而获得该给定索引的字符。

然而，如果我们说：

for offset in 0..<greeting.characters.count {
    let index = greeting.index(greeting.startIndex, offsetBy: offset)
    print("\(greeting[index]) ", terminator: "")
}

那将是 O(n ² )，因为我们现在在循环的每次迭代中从起始索引推进索引（更不用说为了获得count字符的开始而进行 O(n) 遍历）。