Estoy tratando de actualizar mis conocimientos (y espero aprender más) sobre Análisis de Algoritmo. Tomé un curso sobre esto hace dos años, pero estoy tratando de ponerse al día con lo que yo había aprendido en aquel entonces.
La forma en que estoy haciendo es haciendo ejercicios desde el clásico texto de Introducción a los Algoritmos, 2da Edición - CLRS.
El problema que estoy tratando de resolver es este:
Ejercicio 7.2-2
¿Cuál es el tiempo de ejecución de QUICKSORT, cuando todos los elementos de la matriz a tienen el mismo valor?
Mi Solución
El tiempo de ejecución de QUICKSORT, cuando todos los elementos de la matriz a tienen el mismo valor será equivalente al peor de los caso se ejecuta de QUICKSORT ya que no importa lo que el pivote es elegido, QUICKSORT tendrá que ir a través de todos los valores de A. Y desde todos los valores son los mismos, cada llamada recursiva se llevan a desequilibrada de partición.
Así, la repetición será:
$$T(n) = T(n-1) + \Theta(n)$$
El de arriba recurrencia tiene la solución (voy a probar esto más adelante):
$$T(n) = \Theta(n^2)$$
Por lo tanto el tiempo de ejecución de QUICKSORT en este caso es $$\Theta(n^2)$$
Por favor, compruebe si me ha contestado correctamente la pregunta :)
Por favor, hágamelo saber si esta pregunta debe ser publicado en otra parte en el SE de la red.
Gracias!
Jake Clawson
