Frage Ist diese Zeitkomplexität tatsächlich O (n ^ 2)?


Ich arbeite an einem Problem mit CTCI.

Das dritte Problem von Kapitel 1 haben Sie eine Zeichenfolge wie

'Mr John Smith '

und bittet Sie, die Zwischenräume durch zu ersetzen %20:

'Mr%20John%20Smith'

Der Autor bietet diese Lösung in Python an und nennt sie 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

Meine Frage:

Ich verstehe, dass dies O (n) in Bezug auf das Scannen durch die tatsächliche Zeichenfolge von links nach rechts ist. Aber sind Strings in Python nicht unveränderbar? Wenn ich einen String habe und ich füge einen anderen String hinzu + Operator, teilt es nicht den erforderlichen Speicherplatz zu, kopiert das Original und kopiert dann die anhängende Zeichenfolge?

Wenn ich eine Sammlung von n Strings jeder Länge 1, dann dauert das:

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

oder O (n ^ 2) Zeit, ja? Oder irre ich mich, wie Python das Anhängen behandelt?

Alternativ, wenn Sie bereit wären, mir beizubringen, wie man fischt: Wie würde ich das selbst herausfinden? Bei meinen Versuchen, Google eine offizielle Quelle zu finden, war ich nicht erfolgreich. ich fand https://wiki.python.org/moin/TimeComplexity aber das hat nichts an Saiten.


75
2017-11-30 21:06


Ursprung


Antworten:


In CPython, der Standardimplementierung von Python, gibt es ein Implementierungsdetail, das normalerweise O (n) implementiert der Code, den die Bytecode-Auswertungsschleife benötigt + oder += mit zwei Stringoperanden. Wenn Python erkennt, dass das linke Argument keine anderen Referenzen hat, ruft es auf realloc Versuchen Sie, eine Kopie zu vermeiden, indem Sie die Zeichenfolge an der richtigen Stelle ändern. Darauf sollten Sie sich nie verlassen, denn es ist ein Implementierungsdetail und weil, wenn realloc Am Ende muss die Saite häufig bewegt werden, die Leistung verschlechtert sich trotzdem zu O (n ^ 2).

Ohne das seltsame Implementierungsdetail ist der Algorithmus O (n ^ 2) aufgrund des quadratischen Kopierumfangs. Code wie dieser würde nur in einer Sprache mit veränderbaren Strings, wie C ++, und sogar in C ++, die Sie verwenden möchten, Sinn machen +=.


68
2017-11-30 21:20



Der Autor verlässt sich auf eine Optimierung, die zufällig hier ist, aber nicht explizit zuverlässig ist. strA = strB + strC ist typisch O(n), macht die Funktion O(n^2). Es ist jedoch ziemlich einfach sicherzustellen, dass es der gesamte Prozess ist O(n), benutze ein Array:

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

Kurz gesagt, die append Operation ist amortisiert  O(1), (obwohl Sie es stark machen können O(1) indem Sie das Array auf die richtige Größe vorbelegen), indem Sie die Schleife erstellen O(n).

Und dann die join ist auch O(n), aber das ist okay, weil es außerhalb der Schleife ist.


32
2017-11-30 21:28



Ich habe diesen Textschnipsel gefunden Python Speed> Verwenden Sie die besten Algorithmen und schnellsten Tools:

String Verkettung ist am besten mit gemacht ''.join(seq) was ist ein O(n) verarbeiten. Im Gegensatz dazu verwenden Sie die '+' oder '+=' Betreiber können zu einem führen O(n^2) Prozess, da für jeden Zwischenschritt neue Strings erstellt werden können. Der CPython 2.4-Interpreter mildert dieses Problem etwas; jedoch, ''.join(seq) bleibt die beste Praxis


24
2017-11-30 21:26



Für zukünftige Besucher: Da es sich um eine CTCI-Frage handelt, ist jeglicher Bezug auf das Lernen wichtig urllib Paket ist hier nicht erforderlich, speziell nach OP und dem Buch geht es bei dieser Frage um Arrays und Strings.

Hier ist eine vollständigere Lösung, inspiriert von @ njzk2's Pseudo:

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'))

0
2018-03-26 07:47