¿Es esta complejidad de tiempo realmente O (n ^ 2)?

Estoy trabajando en un problema de CTCI.

El tercer problema del capítulo 1 hace que tomes 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 a través de 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 n cadenas cada una de longitud 1, entonces eso toma:

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

o O (n ^ 2) tiempo, ¿sí? ¿O me equivoco en cómo Python se encarga de agregar?

Alternativamente, si estuvieras dispuesto a enseñarme a pescar: ¿Cómo me ocuparía de encontrar esto por mí mismo? No he tenido éxito en mis bashs 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 sea O (n), implementado en el código que el bucle de evaluación de bytecode solicita + o += con dos operandos de cadena . Si Python detecta que el argumento de la izquierda no tiene otras referencias, llama a realloc para 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 realloc necesita mover la cadena con frecuencia, el rendimiento se degrada a O (n ^ 2) de todos modos.

Sin el extraño detalle de la 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 ++, querría usar += .

El autor se basa en una optimización que está aquí, pero no es explícitamente confiable. strA = strB + strC suele ser O(n) , lo que hace que 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 operación de append se amortiza O(1) , (aunque puede hacer que sea fuerte O(1) asignando previamente la matriz al tamaño correcto), haciendo que el bucle O(n) .

Y luego la join también es O(n) , pero está bien porque está fuera del bucle.

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

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

Para futuros visitantes: como se trata de una pregunta CTCI, aquí no se requiere ninguna referencia para aprender el paquete urllib , específicamente según OP y el libro, esta pregunta es sobre Arrays and Strings.

Aquí hay una solución más completa, inspirada en el pseudo @ 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] == ' ': # ns 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'))