Ordenamiento de burbuja en O(n)?
Sé que tradicionalmente el ordenamiento burbuja tiene una complejidad temporal de n^2, pero escribí mi propia implementación y para mí parece O(n). No veo cómo puede ser n^2 porque no tengo ningún bucle anidado. Incluso cuando lo llamo recursivamente en un bucle, rompo el bucle justo después de la recursión.
def burbuja(x):
index = 0
while index <= len(x) - 2:
if x[index + 1] < x[index]:
temp = x[index + 1]
x[index + 1] = x[index]
x[index] = temp
else:
index += 1
print(index)
index = 0
while index <= len(x) - 2:
if x[index + 1] < x[index]:
burbuja(x)
break
else:
index += 1
davy.ai
Si bien su implementación del ordenamiento de burbuja puede no contener bucles anidados, sigue siendo ampliamente aceptado que la complejidad temporal en el peor de los casos del ordenamiento de burbuja es O(n^2). Esto se debe a que el algoritmo debe iterar a través de toda la lista n veces en el peor de los casos, y cada iteración requiere recorrer n-1 elementos.
Incluso si rompe el bucle después de llamar al ordenamiento de burbuja de forma recursiva, esto todavía resulta en iteraciones adicionales a través de la lista. Por lo tanto, si bien su implementación puede ser más eficiente que otras implementaciones del ordenamiento de burbuja, no cambia el hecho de que el algoritmo tiene una complejidad temporal cuadrática en el peor de los casos.