Zeit Komplexität der String-Verkettung in Python

Question

Ich analysiere die Komplexität meines Codes. Aus was ich online gefunden habe, da Strings in Python unveränderlich sind, sollte eine Verkettung eines Strings und eines Zeichens O (len (string) + 1) sein.

Nun, hier ist mein Stück Code (vereinfacht):

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

Die Gesamtzeit Komplexität sein sollte:

(0 + 1) + (1 + 1) + ... + m = m (m + 1)/2 = O (m^2)

Ist das korrekt?

Answer 1

Ja, in Ihrem Fall ^{* 1} Zeichenfolge Verkettung erfordert alle Zeichen kopiert werden, dies ist eine O (N + M) -Operation (wobei N und M sind die Größen der Eingabezeichenfolgen). M, die mit dem gleichen Wort angehängt sind, werden zu O (M^2) Zeit neigen.

Sie können dieses quadratische Verhalten vermeiden, indem str.join() mit:

word = ''.join(list_of_words) 

, die nur dauert O (N) (wobei N die Gesamtlänge des Ausgangs ist). Oder, wenn Sie ein einzelnes Zeichen wiederholen, können Sie verwenden:

word = m * char 

Sie sind Voranstellen Zeichen, sondern der Aufbau eine Liste zuerst, dann ist es umgekehrt (oder mit einem collections.deque() Objekt erhalten O (1) vorangestellt Verhalten) wäre immer noch O (n) -Komplexität, leicht schlagen Sie Ihre O (N^2) Wahl hier.

---

^{* 1} Ab Python 2.4, vermeidet die CPython Implementierung ein neues String-Objekt erstellen, wenn strA += strB oder strA = strA + strB verwenden, aber diese Optimierung ist sowohl zerbrechlich und nicht tragbar. Da Sie strA = strB + strA (vor) verwenden, gilt die Optimierung nicht.