Cuál es la complejidad de tiempo O(n) para la función de reemplazo utilizando tres veces en Python?
Estoy tratando de encontrar la complejidad temporal (Big O) de la función incorporada str.replace() en Python.
Sé que en el peor de los casos, el tiempo es O(n*m) para encontrar una subcadena, pero ¿qué sucede si usamos replace tres veces en una línea?
newstr = str1.replace(char1,’‘).replace(char2,char1).replace(““,char2)
Estoy tratando de intercambiar char1 y char2 en una cadena, el código alternativo utiliza un bucle for, que tiene una complejidad temporal O(n).
Pero, ¿en el código anterior, el Big O se multiplicará por 3, o se convertirá en n^3?
¿tiene eso sentido?
davy.ai
La complejidad temporal (Big O) de la función interna str.replace() en Python es O(nm) en el peor de los casos para encontrar una subcadena. Sin embargo, si usamos reemplazar tres veces en una sola línea, como se muestra en el fragmento de código proporcionado, la complejidad temporal no se multiplicará por 3. La complejidad temporal seguirá siendo O(nm), ya que cada operación de reemplazo es independiente de las demás y la longitud de la cadena permanece igual. Por lo tanto, la complejidad temporal general del fragmento de código proporcionado es O(n*m). No tiene sentido decir que la complejidad temporal del código se convierte en n^3 porque no existe una relación cúbica entre n y el número de operaciones de reemplazo realizadas.