Cette complexité temporelle est-elle réellement O (n ^ 2)?

Question

Je suis en train de travailler sur un problème de la CTCI.

Le troisième problème, chapitre 1, a vous de prendre une chaîne telle que

'Mr John Smith '

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

'Mr%20John%20Smith'

L'auteur propose cette solution en Python, le qualifiant de 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 numérisation par le biais de la chaîne de gauche à droite. Mais ne sont pas des chaînes de caractères en Python immuable? Si j'ai un string et j'ajoute une autre corde à l'aide de l' + de l'opérateur, n'est-ce pas allouer l'espace nécessaire, la copie à l'original, et puis les copier sur l'ajout de la chaîne?

Si j'ai une collection de n cordes de longueur 1, puis qui prend:

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

ou O(n^2) temps, oui? Ou suis-je trompé dans la façon Python gère ajoutant?

Alternativement, si vous seriez prêt à m'enseigner comment pêcher: Comment pourrais-je aller sur la recherche de ce pour moi? J'ai échoué dans mes tentatives de Google une source officielle. J'ai trouvé https://wiki.python.org/moin/TimeComplexity mais cela ne veut pas avoir quoi que ce soit sur les chaînes de caractères.

Answer 1

Dans Disponible, la mise en œuvre standard de Python, il y a un détail d'implémentation qui rend cette habitude O(n), mis en œuvre dans le code du bytecode à la boucle d'évaluation des appels pour + ou += avec chaîne de deux opérandes. Si Python détecte que la gauche argument n'a pas d'autres références, il appelle realloc pour tenter d'éviter une copie par le redimensionnement de la chaîne en place. Ce n'est pas quelque chose que vous devez jamais compter sur, parce que c'est un détail d'implémentation, et parce que si realloc finit par avoir besoin de déplacer la chaîne fréquemment, les performances se dégradent à O(n^2), de toute façon.

Sans l'étrange détail de l'implémentation, l'algorithme est O(n^2) en raison de l'équation de quantité de reproduction. Code comme celui-ci n'a de sens que dans une langue avec les cordes mutables, comme C++, et même en C++, vous voulez les utiliser +=.

Answer 2

L'auteur s'appuie sur une optimisation qui se trouve être ici, mais n'est pas explicitement fiable. strA = strB + strC est typiquement O(n), faisant de la fonction O(n^2). Toutefois, il est assez facile de s'assurer que tout le processus est - O(n), l'utilisation d'un tableau:

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

En un mot, l' append opération est amorti O(1), (bien que vous pouvez faire fort O(1) par pré-allouer le tableau à la bonne taille), faire la boucle O(n).

Et puis l' join également O(n), mais c'est bien parce que c'est en dehors de la boucle.

Answer 3

J'ai trouvé cet extrait de texte sur Python Vitesse > Utiliser les meilleurs algorithmes et la plus rapide d'outils:

La concaténation de chaîne est préférable de faire avec ''.join(seq) qui est un O(n) processus. En revanche, à l'aide de l' '+' ou '+=' opérateurs peuvent entraîner une O(n^2) processus, car les nouvelles chaînes peut être construit pour chaque étape intermédiaire. Le Disponible 2.4 interprète atténue cette question quelque peu; cependant, ''.join(seq) reste la meilleure pratique