在不同表示形式中获取字符串长度的运行时复杂性 [英] Runtime complexity of getting the length of a string in different representations

问题描述

在Swift 2中，给定字符串s，这些语句的运行时复杂度是什么:

In Swift 2, given a string s, what's the runtime complexity of these statements:

s.characters.count
s.endIndex
s.utf8.count
s.utf16.count
s.unicodeScalars.count

此外，如果我知道一个字符串仅包含字母，那么获取第n个字符的最有效方法是什么?

Also, if I know a string contains alphabets only, what's the most efficient way of getting the n-th character?

推荐答案

好的，我正在尝试回答我自己的问题.如果我错了，请随时纠正我.

OK, I'm trying to answer my own question. Feel free to correct me if I'm wrong.

s.characters.count  // O(N)
s.endIndex // O(1)
s.utf8.count // O(N)
s.utf16.count // O(N)
s.unicodeScalars.count // O(N)

Apple的 CollectionType.count 上的文档说:复杂度:如果Index符合RandomAccessIndexType，则为O(1)；否则为O(N)."由于CharacterView，UnicodeScalarView，UTF16View或UTF8View的Index都不符合RandomAccessIndexType，因此访问它们的计数都为O(N).

Apple's documentation on CollectionType.count says "Complexity: O(1) if Index conforms to RandomAccessIndexType; O(N) otherwise." Since none of the Index of CharacterView, UnicodeScalarView, UTF16View or UTF8View conforms to RandomAccessIndexType, accessing their counts are all O(N).

这篇关于在不同表示形式中获取字符串长度的运行时复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！