如果T.Index是RandomAccessIndexType，countElements的運行時複雜度是多少？

計算String的字符時countElements函數的運行時複雜度是多少？如果T.Index是RandomAccessIndexType，countElements的運行時複雜度是多少？

文檔說：

O（1）如果是T.Index RandomAccessIndexType;否則爲O（N）。

什麼是RandomAccessIndexType？ String是一個RandomAccessIndexType？

2014-11-02 schirrmacher

因此到的文檔：

索引可以通過位置的任意數量的偏移量，並且可以測量到任何可到達的值的距離，在O（1）

夫特字符串（不幸）不要實現它。他們使用BidirectionalIndexType來代替，這基本上使字符串成爲一個雙向鏈接列表，這意味着爲了達到位置n位置m處的字符，它將瀏覽它們之間的所有元素。因此，字符串的countElements函數具有複雜性O（n）

來源

2014-11-02 21:40:30 Antonio

要添加其他信息，String不是RandomAccessIndexType，因爲String支持擴展的字形羣集，這意味着必須迭代字符串才能找到「元素」，它表示整個字形集羣，而不僅僅是單個字形（例如組合字符/口音等）。 – 2014-11-02 21:43:40

另外，因爲String是在平面1和以上的UTF-16字符中實現的，所以需要兩個UTF-16代碼單元。大多數表情符號在平面1中。這與NSString沒有什麼不同。當您在Swift字符串上訪問時，NSString的'length'屬性已被重命名爲'utf16Count'。 'NSString'' length'屬性返回UTF-16代碼單元的數量（'unichar'），而不是字符數。 – zaph 2014-11-02 22:13:14

如果T.Index是RandomAccessIndexType，countElements的運行時複雜度是多少？

回答

相關問題