Pythonでの文字列連結の時間の複雑さ

Question

私のコードの複雑さを分析しています。 文字列と文字の連結は、O（len（string）+ 1）にする必要があります。

word = "" 
for i in range(m): 
    word = char_value + word 
return word 

合計時間の複雑さは、次のようになります：

は今、ここに私の（簡体字）コードの一部です

（0 + 1）+（1 + 1）+ ... + m = m（m + 1）/ 2 = O（m^2）

これは間違いありませんか？

Answer 1

はい、あなたのケースで* 1 文字列の連結をコピーするすべての文字を必要とし、これは（N及びMは、入力文字列のサイズである）O（N + M）動作です。同じ単語のM個の付加はO（M^2）時間になる。

あなたがstr.join()を使用して、この二次現象を回避することができる：

word = ''.join(list_of_words) 

のみO（N）（Nは出力の合計の長さ）とります。それとも、単一の文字を繰り返している場合は、あなたが使用することができます。

word = m * char 

あなたはそれを逆転させる（またはO（1）前に付ける動作を取得するためにcollections.deque()オブジェクトを使用して）、文字を付加ますが、最初のリストを作成していますあなたのO（N^2）の選択をここで簡単に打ち負かすことは、依然としてO（n）の複雑さです。 strA += strBまたはstrA = strA + strBを使用した場合のPython 2.4のよう

---

^{* 1}

は、CPythonの実装は、新しい文字列オブジェクトを作成することを回避するが、この最適化は、壊れやすく、ポータブルではないの両方です。 strA = strB + strA（prepending）を使用しているため、最適化は適用されません。