¿La complejidad de tiempo de la cadena iterativa anexa es realmente O (n ^ 2) u O (n)?

Estoy trabajando en un problema de CTCI.

El tercer problema del capítulo 1 tiene que tomar una cadena como

'Mr John Smith '

y le pide que reemplace los espacios intermedios con %20:

'Mr%20John%20Smith'

El autor ofrece esta solución en Python, llamándola 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

Mi pregunta:

Entiendo que esto es O (n) en términos de escanear la cadena real de izquierda a derecha. ¿Pero no son inmutables las cadenas en Python? Si tengo una cadena y le agrego otra cadena con el +operador, ¿no asigna el espacio necesario, copia sobre el original y luego copia sobre la cadena adjunta?

Si tengo una colección de ncadenas de cada uno de longitud 1, entonces eso requiere:

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

o O (n ^ 2) tiempo , ¿sí? ¿O me equivoco en cómo Python maneja la agregación?

Alternativamente, si estuvieras dispuesto a enseñarme a pescar: ¿Cómo haría para descubrir esto por mí mismo? No he tenido éxito en mis intentos de buscar en Google una fuente oficial. Encontré https://wiki.python.org/moin/TimeComplexity pero esto no tiene nada en las cadenas.

En CPython, la implementación estándar de Python, hay un detalle de implementación que hace que esto generalmente sea O (n), implementado en el código que el ciclo de evaluación de código de bytes llama +o +=con dos operandos de cadena . Si Python detecta que el argumento de la izquierda no tiene otras referencias, llama reallocpara intentar evitar una copia cambiando el tamaño de la cadena en su lugar. Esto no es algo en lo que deba confiar, porque es un detalle de implementación y porque si realloctermina necesitando mover la cadena con frecuencia, el rendimiento se degrada a O (n ^ 2) de todos modos.

Sin el extraño detalle de implementación, el algoritmo es O (n ^ 2) debido a la cantidad cuadrática de copia involucrada. Un código como este solo tendría sentido en un lenguaje con cadenas mutables, como C ++, e incluso en C ++ que le gustaría usar +=.

El autor se basa en una optimización que se encuentra aquí, pero que no es explícitamente confiable. strA = strB + strCes típicamente O(n), haciendo la función O(n^2). Sin embargo, es bastante fácil asegurarse de que todo el proceso sea O(n), use una matriz:

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

En pocas palabras, la appendoperación se amortiza O(1) (aunque puede fortalecerla O(1)asignando previamente la matriz al tamaño correcto), creando el bucle O(n).

Y luego jointambién es O(n), pero está bien porque está fuera del ciclo.

Encontré este fragmento de texto en Python Speed> Use los mejores algoritmos y las herramientas más rápidas :

La concatenación de cadenas se realiza mejor con lo ''.join(seq)que es un O(n)proceso. En contraste, el uso de los operadores '+'o '+='puede resultar en un O(n^2)proceso porque se pueden construir nuevas cadenas para cada paso intermedio. El intérprete CPython 2.4 mitiga un poco este problema; sin embargo, ''.join(seq)sigue siendo la mejor práctica

Para futuros visitantes: dado que es una pregunta de CTCI, aquí no se requiere ninguna referencia al aprendizaje del paquete urllib , específicamente según OP y el libro, esta pregunta es sobre Arrays y Strings.

Aquí hay una solución más completa, inspirada en el 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'))