Análisis de algoritmos

En informática, el análisis de algoritmos es la determinación de la cantidad de recursos (como el tiempo y el almacenamiento) necesarios para ejecutarlos. La mayoría de los algoritmos están diseñados para trabajar con entradas de longitud arbitraria. Por lo general, la eficacia o el tiempo de funcionamiento de un algoritmo se expresa como una función que relaciona la longitud de entrada para el número de pasos (complejidad de tiempo) o lugares de almacenamiento (complejidad espacio).
Algoritmo de análisis es una parte importante de una teoría de la complejidad computacional más amplio, que proporciona estimaciones teóricas para los recursos necesarios por cualquier algoritmo que resuelve un problema computacional dado. Estas estimaciones dan una idea de las instrucciones razonables de búsqueda de algoritmos eficientes.
En el análisis teórico de los algoritmos es común para estimar su complejidad en el sentido asintótico, es decir, para estimar la función de la complejidad para arbitrariamente grande de entrada. Cota superior asintótica, notación omega-Grande y la notación Big-theta se utilizan para este fin. Por ejemplo, se dice que la búsqueda binaria para funcionar en una serie de pasos proporcional al logaritmo de la longitud de la lista que se busca, o en O (log (n)), coloquialmente "en el tiempo logarítmica". Por lo general, las estimaciones asintóticas se utilizan debido a que diferentes implementaciones del mismo algoritmo pueden diferir en la eficiencia. Sin embargo, las eficiencias de las dos implementaciones "razonables" de un algoritmo dado están relacionadas por un factor multiplicativo constante llamada Ahidden constante.
Medidas exactas (no asintóticas) de eficiencia a veces pueden ser calculadas pero por lo general requieren ciertas suposiciones con respecto a la implementación particular del algoritmo, llamado modelo de computación. Un modelo de cálculo puede ser definido en términos de un ordenador abstracto, por ejemplo, máquina de Turing, y / o postulando que ciertas operaciones se ejecutan en la unidad de tiempo. Por ejemplo, si la lista ordenada a la que aplicará búsqueda binaria tiene n elementos, y podemos garantizar que cada búsqueda de un elemento en la lista se puede realizar en la unidad de tiempo, a continuación, a lo sumo log2 n se necesitan + 1 unidades de tiempo para volver una respuesta.

https://en.wikipedia.org/wiki/Analysis_of_algorithms