Czy złożoność czasowa iteracyjnego łańcucha jest faktycznie dołączana O (n ^ 2), czy O (n)?

Pracuję nad problemem z CTCI.

Trzeci problem z rozdziału 1 polega na tym, że bierzesz ciąg, taki jak

'Mr John Smith '

i prosi o zastąpienie spacji pośrednich %20:

'Mr%20John%20Smith'

Autor oferuje takie rozwiązanie w Pythonie, nazywając je 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

Moje pytanie:

Rozumiem, że jest to O (n) pod względem przeglądania rzeczywistego ciągu od lewej do prawej. Ale czy łańcuchy w Pythonie nie są niezmienne? Jeśli mam ciąg i dodam do niego kolejny ciąg z +operatorem, czy nie przydziela on niezbędnej przestrzeni, nie kopiuje oryginału, a następnie kopiuje dołączany ciąg?

Jeśli mam kolekcję nciągów o długości 1, to przyjmuje:

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

lub O (n ^ 2) czas , tak? A może mylę się co do tego, jak Python obsługuje dołączanie?

Ewentualnie, gdybyś zechciał nauczyć mnie łowić ryby: jak bym się tego nauczył? Nie udało mi się znaleźć oficjalnego źródła w Google. Znalazłem https://wiki.python.org/moin/TimeComplexity, ale to nie ma nic na łańcuchach.

W CPythonie, standardowej implementacji Pythona, istnieje szczegół implementacji, który sprawia, że ​​zwykle jest to O (n), zaimplementowane w kodzie, w którym pętla oceny kodu bajtowego wywołuje +lub +=z dwoma operandami łańcuchowymi . Jeśli Python wykryje, że lewy argument nie ma innych odniesień, wywołuje reallocpróbę uniknięcia kopii, zmieniając rozmiar ciągu w miejscu. Nie jest to coś, na czym powinieneś zawsze polegać, ponieważ jest to szczegół implementacji, a ponieważ jeśli w reallockońcu będziesz musiał często przesuwać ciąg, wydajność i tak spada do O (n ^ 2).

Bez dziwnych szczegółów implementacji algorytm ma wartość O (n ^ 2) ze względu na kwadratową wielkość kopiowania. Taki kod miałby sens tylko w języku ze zmiennymi łańcuchami, jak C ++, a nawet w C ++, którego chciałbyś użyć +=.

Autor polega na optymalizacji, która jest tutaj, ale nie jest wyraźnie niezawodna. strA = strB + strCjest zazwyczaj O(n)tworzeniem funkcji O(n^2). Jednak dość łatwo jest upewnić się, że cały proces jest taki sam O(n), użyj tablicy:

output = []
    # ... loop thing
    output.append('%20')
    # ...
    output.append(char)
# ...
return ''.join(output)

Krótko mówiąc, appendoperacja jest amortyzowana O(1) (chociaż można ją wzmocnić O(1), wstępnie przydzielając tablicę do odpowiedniego rozmiaru), tworząc pętlę O(n).

A potem joinjest również O(n), ale to jest w porządku, ponieważ jest poza pętlą.

Znalazłem ten fragment tekstu w Python Speed> Użyj najlepszych algorytmów i najszybszych narzędzi :

Najlepiej jest wykonywać konkatenację ciągów, w przypadku ''.join(seq)których jest to O(n)proces. W przeciwieństwie do tego, użycie operatorów '+'lub '+='może spowodować powstanie O(n^2)procesu, ponieważ dla każdego kroku pośredniego mogą być budowane nowe łańcuchy. Interpreter CPythona 2.4 nieco łagodzi ten problem; jednak ''.join(seq)pozostaje najlepszą praktyką

Dla przyszłych odwiedzających: ponieważ jest to pytanie CTCI, wszelkie odniesienia do uczenia się urllib pakietu nie jest tutaj wymagane, szczególnie zgodnie z OP i książką, to pytanie dotyczy tablic i ciągów.

Oto bardziej kompletne rozwiązanie, zainspirowane pseudo @ njzk2:

text = 'Mr John Smith'#13 
special_str = '%20'
def URLify(text, text_len, special_str):
    url = [] 
    for i in range(text_len): # O(n)
        if text[i] == ' ': # n-s
            url.append(special_str) # append() is O(1)
        else:
            url.append(text[i]) # O(1)

    print(url)
    return ''.join(url) #O(n)


print(URLify(text, 13, '%20'))