Page 71 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Figura 2.4. Peor caso para quick sort

Como se observa en la figura 2.4, no se tiene recursividad izquierda, y para la recursividad derecha
cada llamada se realiza con un elemento menos:
~
C = n+(n-1) + (n-2) + (n-3) +…+2 ~n*(n-1) /2 (observar el método de inserción binaria) o:
máx
T(n) = T (1) + T(n-1) + n

T(n) =T (1) + T (1) + T(n-2) + n + (n-1)

T(n) = T (1) + T (1) + T (1) + T(n-3) + n + (n-1) + (n-2)

…

T(n) = T (1) + T (1) + T (1) + … T(1) + T(2) + n + (n-1) + (n-2) + … + 3

T(n)= n + (n-1) + (n-2) +… + 3 +2.

Utilizando una adaptación del truco de Gauss, se obtiene:
T(n) = O (n ).
2
En el mejor caso, cuando existe una buena partición, se tiene:

K = n / 2

T(n) = 2T(n/2) + O (n)

T(n) = O (nLog(n)),

siendo el análisis análogo al merge sort.

65