Swift 3.0 中使用索引访问字符串的 Big O

访问的复杂度是多少String与index in swift 3.0?

复杂度与数组访问或 O(N) 或其他相同吗？

来自文档 https://developer.apple.com/library/prerelease/content/documentation/Swift/Conceptual/Swift_Programming_Language/StringsAndCharacters.html在“字符串索引”下：

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)，那么它是如何工作的，因为不能仅将偏移量乘以常量来获取内存中的字符？

除非另有说明，否则实施Collection's subscript https://developer.apple.com/reference/swift/collection/1641358-subscript要求should时间复杂度始终为 O(1)。这是合同的一部分Collection itself.

As 文档 https://developer.apple.com/reference/swift/collection状态（强调我的）：

符合的类型Collection预计将提供start​Index and end​Index特性以及以 O(1) 操作对元素进行下标访问。无法保证预期性能的类型必须记录离开 [...]

当你来到时，潜在的昂贵部分就会发生advance索引，例如index(_:offsetBy:) https://developer.apple.com/reference/swift/collection/1781645-index。其复杂度为 O(1)RandomAccessCollection，否则为 O(n)，其中 n 是偏移量的大小。

String.CharacterView https://developer.apple.com/reference/swift/string.characterview不是一个RandomAccessCollection，因此推进索引是 O(n)。正如您所说，其原因是字符可以具有不同的字节长度。但是一旦你有了索引（其中内部 https://github.com/apple/swift/blob/master/stdlib/public/core/StringCharacterView.swift#L169只是字符串的 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: "")
}

That would be O(n²), because we're now advancing the index from the start index at each iteration of the loop (not to mention doing an O(n) walk just to get the count of the characters to begin with).