Page 66 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 66
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Figura 2.2. Método merge sort (University of Pennsylvania. Departament of Engineering)
El tiempo de cómputo para merge sort se describe a continuación:
La recursividad para merge sort requiere:
T(n)=2T(n/2) + O(n),
ya que
• Realizar la recursividad de los dos subarreglos requiere 2T(n/2).
• La ordenación y fusión de los subarreglos requiere 2n O(n). El costo es C .
n
• La base de la recursión es T(1) = 0, ya que es trivial ordenar un arreglo de un
elemento.
60
