La complexité temporelle de l'ajout de chaîne itérative est-elle réellement O (n ^ 2) ou O (n)?

Je travaille sur un problème avec CTCI.

Le troisième problème du chapitre 1 consiste à prendre une chaîne telle que

'Mr John Smith '

et vous demande de remplacer les espaces intermédiaires par %20:

'Mr%20John%20Smith'

L'auteur propose cette solution en Python, en l'appelant 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

Ma question:

Je comprends que c'est O (n) en termes de balayage de la chaîne réelle de gauche à droite. Mais les chaînes en Python ne sont-elles pas immuables? Si j'ai une chaîne et que j'y ajoute une autre chaîne avec l' +opérateur, n'alloue-t-elle pas l'espace nécessaire, ne copie-t-elle pas l'original, puis ne copie-t-elle pas la chaîne d'ajout?

Si j'ai une collection de nchaînes chacune de longueur 1, alors cela prend:

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

ou O (n ^ 2) fois , oui? Ou est-ce que je me trompe sur la façon dont Python gère l'ajout?

Sinon, si vous êtes prêt à m'apprendre à pêcher: comment pourrais-je le découvrir par moi-même? J'ai échoué dans mes tentatives pour rechercher une source officielle sur Google. J'ai trouvé https://wiki.python.org/moin/TimeComplexity mais cela n'a rien sur les chaînes.

Dans CPython, l'implémentation standard de Python, il existe un détail d'implémentation qui en fait généralement O (n), implémenté dans le code que la boucle d'évaluation de bytecode appelle +ou +=avec deux opérandes de chaîne . Si Python détecte que l'argument de gauche n'a pas d'autres références, il appelle reallocpour tenter d'éviter une copie en redimensionnant la chaîne sur place. Ce n'est pas quelque chose sur lequel vous devriez jamais vous fier, car c'est un détail d'implémentation et parce que si vous devez reallocdéplacer la chaîne fréquemment, les performances se dégradent de toute façon à O (n ^ 2).

Sans les détails d'implémentation étranges, l'algorithme est O (n ^ 2) en raison de la quantité quadratique de copie impliquée. Un code comme celui-ci n'aurait de sens que dans un langage avec des chaînes mutables, comme C ++, et même en C ++ que vous voudriez utiliser +=.

L'auteur s'appuie sur une optimisation qui se trouve ici, mais qui n'est pas explicitement fiable. strA = strB + strCest généralement O(n), faire la fonction O(n^2). Cependant, il est assez facile de s'assurer que tout le processus est O(n), utilisez un tableau:

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

En un mot, l' appendopération est amortie O(1) (bien que vous puissiez la rendre forte O(1)en pré-allouant le tableau à la bonne taille), ce qui fait la boucle O(n).

Et puis joinc'est aussi O(n), mais ce n'est pas grave car c'est en dehors de la boucle.

J'ai trouvé cet extrait de texte sur Python Speed> Utilisez les meilleurs algorithmes et les outils les plus rapides :

La concaténation de chaînes est mieux effectuée avec ''.join(seq)un O(n)processus. En revanche, l'utilisation des opérateurs '+'ou '+='peut entraîner un O(n^2)processus car de nouvelles chaînes peuvent être créées pour chaque étape intermédiaire. L'interpréteur CPython 2.4 atténue quelque peu ce problème; cependant, ''.join(seq)reste la meilleure pratique

Pour les futurs visiteurs: Puisqu'il s'agit d'une question CTCI, aucune référence à l'apprentissage du package urllib n'est requise ici, en particulier selon OP et le livre, cette question concerne les tableaux et les chaînes.

Voici une solution plus complète, inspirée du pseudo de @ 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'))