在不同表示形式中获取字符串长度的运行时复杂性 [英] 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屋!