Evaluación de algoritmo Merge Sort | Big O notation
En esta historia veremos como se calcula el trabajo del algoritmo Merge Sort.
El primer paso es calcular el esfuerzo por cada operación:
= No de niveles * Tamaño de cada sub operación
= 2^j * n(n/2^j)
= n*n
El segundo paso es calcular el esfuerzo de todas las operaciones
= Esfuerzo por nivel * No de niveles
= (n*n) * (log2n +1)
El resultado en notación Big O
=> O (n log n)
Otro tipo de notaciones son:
O(n) = cuando el algoritmo se explica como una función lineal
Básicamente significa que se aplica una función de un solo paso, como sustituir un valor. Ej. f(n) =4n
O(n²) = cuando se tienen ciclos en el código (loops)
Es porque para cada paso se esta llamando otra función. Esto pasa en for anidados, para cada paso del primer for vamos a ejecutar varias veces el segundo for.
