[解決済み] 文字列の反復加算の時間計算量はO(n^2)なのかO(n)なのか？

質問

CTCIの問題に取り組んでいます。

第1章の3番目の問題では、次のような文字列を取ることになっています。

'Mr John Smith '

で、中間的なスペースを %20 :

'Mr%20John%20Smith'

著者はこの解決策をPythonで提供し、O(n)と呼んでいます。

def urlify(string, length):
    '''function replaces single spaces with %20 and removes trailing spaces'''
    counter = 0
    output = ''
    for char in string:
        counter += 1
        if counter > length:
            return output
        elif char == ' ':
            output = output + '%20'
        elif char != ' ':
            output = output + char
    return output

私の質問です。

実際の文字列を左から右へスキャンする点で、これがO(n)であることは理解しています。しかし、Pythonの文字列は不変ではないのでしょうか？もし私が文字列を持っていて、それに別の文字列を + 演算子で別の文字列を追加する場合、必要なスペースを確保し、元の文字列をコピーし、そして追加する文字列をコピーするのではないでしょうか？

のコレクションがある場合 n 文字列のコレクションがあるとします。

1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2

または O(n^2)時間 ということですか？それとも、Pythonが追加を処理する方法について私が間違っているのでしょうか？

あるいは、もしあなたが私に釣りの仕方を教えてくれるなら、自分自身でこれを見つけるにはどうしたらいいでしょうか？私は公式ソースをググろうと試みましたが、うまくいきませんでした。私が見つけたのは https://wiki.python.org/moin/TimeComplexity を見つけましたが、これには文字列に関するものはありません。

どのように解決するのですか？

Pythonの標準実装であるCPythonでは、これを通常O(n)にする実装があり、その実装を バイトコード評価ループが呼び出すコード + または += 2つの文字列オペランドを持つ . Pythonが左の引数が他の参照を持っていないことを検出した場合、それは realloc を呼び出し、その場で文字列のサイズを変更することでコピーを回避しようとします。これは実装の詳細であるため、決して頼るべきものではありません。 realloc が頻繁に文字列を移動する必要がある場合、パフォーマンスはいずれにせよ O(n^2) まで低下するからです。

奇妙な実装の詳細がなければ、アルゴリズムは、関係するコピーの二次的な量のためにO(n^2)になります。このようなコードは、C++ のような変更可能な文字列を持つ言語でのみ意味をなしますが、C++ でも += .