 |
 |
|
El siguiente es el arbol de recursion para el algoritmo MERGE-SORT sobre un arreglo de 16 elementos, la construccion de este arbol comienza teniendo un problema
El primer nivel del algoritmos es dado por problemas de n/2, el siguiente nivel es de problemas de n/4, luego de n/8 y finalmente de n/16 es decir problemas de T(1): dando como resultado: T(n) = 2T(n/2) + cn = 2( 2T(n/4)+cn/2) + cn = 4(2T(n/8) + cn/4 ) + cn +cn ____= 8(2T(n/16)+cn/8) + cn + cn + cn = 16T(n/16) + 4cn
Memoization es inefectivo para el algoritmo de MERGE-SORT, ya que este no necesita almacenar algun valor de alguna solucion, simplemente por que la estructura del Merge-Sort no utilizara los valores anteriormente encontrado mas de una vez, por esta razon memoization no tendra algun efecto en tiempo de ejecucion. |
 |
|
