¿La complejidad temporal de la adición de cadena iterativa es realmente O (n ^ 2) u O (n)?
Estoy trabajando en un problema fuera de CTCI.
El tercer problema del capítulo 1 consiste en tomar una cuerda 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, cada una de ellas de longitud 1, entonces eso requiere:
1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2
o O(n^2) tiempo , ¿no? ¿O me equivoco en cómo maneja Python las anexiones?
Alternativamente, si estuviera dispuesto a enseñarme a pescar: ¿Cómo podría descubrirlo 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 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 sea generalmente O(n), implementado en el código que el bucle de evaluación de código de bytes solicita +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 debas confiar, porque es un detalle de implementación y porque si reallocterminas necesitando mover la cadena con frecuencia, el rendimiento se degrada a O(n^2) de todos modos.
Sin los extraños detalles de implementación, el algoritmo es O(n^2) debido a la cantidad cuadrática de copias involucradas. Un código como este solo tendría sentido en un lenguaje con cadenas mutables, como C++, e incluso en C++ querrás usar +=.
El autor se basa en una optimización que se encuentra aquí, pero que no es explícitamente confiable. strA = strB + strCnormalmente es O(n), haciendo la función O(n^2). Sin embargo, es bastante fácil asegurarse de que todo el proceso sea así O(n): utilice 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 joinis también O(n), pero está bien porque está fuera del bucle.
Encontré este fragmento de texto en Python Speed > Utilice los mejores algoritmos y las herramientas más rápidas :
La concatenación de cadenas se realiza mejor con
''.join(seq)cuál es unO(n)proceso. Por el contrario, el uso de los operadores'+'o'+='puede dar lugar a unO(n^2)proceso porque se pueden crear 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
