¿Por qué la complejidad temporal de los bucles while anidados en el algoritmo Quicksort no es O(n^2)?
def partition(l, h):
i, j = l, h
while i < j:
while arr[l] > arr[i]:
i += 1
while arr[j] > arr[l] and j >= 0:
j += 1
if i < j:
arr[i], arr[j] = arr[j], arr[i]
arr[l], arr[j] = arr[j], arr[l]
return j
La complejidad de tiempo de los bucles while anidados es O(n^2), el código de ejemplo anterior es de Quicksort. ¿Entonces cómo es la complejidad de tiempo total O(n log n)?
davy.ai
La complejidad de tiempo general de Quicksort no está determinada únicamente por los bucles anidados en la función de partición, sino por la combinación de todas las operaciones dentro del algoritmo de Quicksort.
En Quicksort, el algoritmo divide recursivamente el arreglo en sub-arreglos más pequeños y los ordena. La función de partición se utiliza para dividir el arreglo en dos sub-arreglos más pequeños que luego se ordenan recursivamente.
La función de partición tiene una complejidad de tiempo de peor caso de O(n^2) si el arreglo ya está ordenado o casi ordenado, pero en promedio, la función de partición toma O(n) tiempo para completarse.
Sin embargo, cuando combinamos la función de partición con la clasificación recursiva de los sub-arreglos, la complejidad de tiempo general de Quicksort se reduce a O(n log n), lo cual es mucho más rápido que O(n^2).
Esta reducción en la complejidad de tiempo se debe al hecho de que los sub-arreglos tienen tamaños aproximadamente iguales y el algoritmo divide el problema en sub-problemas más pequeños en lugar de procesar repetidamente todo el arreglo.