Eficiencia de un Algoritmo

Tiempo de ejecución de un algoritmo: número de instrucciones simples que se ejecutan o tiempo de ejecución en un ordenador idealizado.
   

è Principio de Invarianza: dos implementaciones distintas de un mismo algoritmo no diferirán en eficiencia más que una constante multiplicativa.
   

Operaciones Elementales: instrucciones cuyo tiempo de ejecución queda limitado superiormente por una constante que sólo depende de la implementación.
   

è Análisis de Eficiencia de un algoritmo: sólo será relevante el número de operaciones primitivas y no su duración.
   

Orden de Eficiencia: un algoritmo necesita un tiempo de ejecución del orden de una función f(n), cuando existe una constante positiva “c” y una implementación que resuelve cada instancia del problema “n” en un tiempo acotado superiormente por c · f(n), siendo f(n) la función que marca cómo crecerá dicho tiempo de ejecución cuando aumente n.
   

è Un algoritmo será más eficiente que otro si el tiempo de ejecución del peor caso tiene un orden de crecimiento menor que el segundo.

Funciones de complejidad algorítmica:

Constante: O(1)

Logarítmica: O(log n)

Lineal: O(n)

Quasilineal: O(n · log n)

Cuadrática: O(n^2)

Cúbica: O(n^3)

Polinómica: O(n^k)

Exponencial: O(k^n)

Factorial: O(n!)