Un algoritmo será mas eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.
La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad:
Complejidad Temporal o Tiempo de ejecución: Tiempo de cómputo necesario para ejecutar algún programa.
Complejidad Espacial: Memoria que utiliza un programa para su ejecución, La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoria estática de un algoritmo se suma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.
Este análisis se basa en las Complejidades Temporales, con este fin, para cada problema determinaremos una medida N, que llamaremos tamaño de la entrada o número de datos a procesar por el programa, intentaremos hallar respuestas en función de dicha N.
El concepto exacto que cuantifica N dependerá de la naturaleza del problema, si hablamos de un array se puede ver a N como el rango del array, para una matriz, el número de elementos que la componen; para un grafo, podría ser el número de nodos o arcos que lo arman, no se puede establecer una regla para N, pues cada problema acarrea su propia lógica y complejidad.
La familia O(f(n)) define un Orden de Complejidad. Elegiremos como representante de este Orden de Complejidad a la función f(n) más sencilla perteneciente a esta familia.
Las funciones de complejidad algorítmica más habituales en las cuales el único factor del que dependen es el tamaño de la muestra de entrada n, ordenadas de mayor a menor eficiencia son:
O(1) | Orden constante |
O(log n) | Orden logarítmico |
O(n) | Orden lineal |
O(n log n) | Orden cuasi-lineal |
O(n2) | Orden cuadrático |
O(n3) | Orden cúbico |
O(na) | Orden polinómico |
O(2n) | Orden exponencial |
O(n!) | Orden factorial |
Se identifica una Jerarquía de Ordenes de Complejidad que coincide con el orden de la tabla mostrada; jerarquía en el sentido de que cada orden de complejidad inferior tiene a las superiores como subconjuntos.
1.
2. O(1): Complejidad constante. Cuando las instrucciones se ejecutan una vez.
3.
4. O(log n): Complejidad logarítmica. Esta suele aparecer en determinados algoritmos con iteración o recursión no estructural, ejemplo la búsqueda binaria.
5.
6. O(n): Complejidad lineal. Es una complejidad buena y también muy usual. Aparece en la evaluación de bucles simples siempre que la complejidad de las instrucciones interiores sea constante.
7.
8. O(n log n): Complejidad cuasi-lineal. Se encuentra en algoritmos de tipo divide y vencerás como por ejemplo en el método de ordenación quicksort y se considera una buena complejidad. Si n se duplica, el tiempo de ejecución es ligeramente mayor del doble.
9.
10. O(n2): Complejidad cuadrática. Aparece en bucles o ciclos doblemente anidados. Si n se duplica, el tiempo de ejecución aumenta cuatro veces.
11.
12. O(n3): Complejidad cúbica. Suele darse en bucles con triple anidación. Si n se duplica, el tiempo de ejecución se multiplica por ocho. Para un valor grande de n empieza a crecer dramáticamente.
13.
14. O(na): Complejidad polinómica (a > 3). Si a crece, la complejidad del programa es bastante mala.
15.
16. O(2n): Complejidad exponencial. No suelen ser muy útiles en la práctica por el elevadísimo tiempo de ejecución. Se dan en subprogramas recursivos que contengan dos o más llamadas internas. N
Algoritmos Polinomiales: Aquellos que son proporcionales a na. Son en general factibles o aplicables, los problemas basados en estos algoritmos son solucionables.
Algoritmos Exponenciales: Aquellos que son proporcionales a kn ", k En general no son factibles salvo un.2 ³ tamaño de entrada n exageradamente pequeño, pero generalmente pertenecen a un universo de problemas de los cuales el cómputo se hace imposible. N
