fbpx
Wikipedia

Análisis de algoritmos

El análisis de algoritmos es una parte importante de la teoría de complejidad computacional, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.

A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica, y las notaciones omega (cota inferior) y theta (caso promedio) se usan con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)), coloquialmente "en tiempo logarítmico". Normalmente, las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen por qué tener la misma eficiencia. No obstante, la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta.

La medida exacta (no asintótica) de la eficiencia a veces puede ser computada, pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda binaria tiene n elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario, entonces se requieren, como mucho, log2 N + 1 unidades de tiempo para devolver una respuesta.

Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos porque tienen más precisión y, así, les permite saber cuánto tiempo pueden suponer que tomará la ejecución. Para algunas personas, como los desarrolladores de videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso.

Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso se encuentra acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertos contextos. Si, por ejemplo, los números involucrados en la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con dos enteros pero de 1000 dígitos cada uno).

Véase también

Bibliografía


  •   Datos: Q333464

análisis, algoritmos, este, artículo, sección, necesita, wikificado, favor, edítalo, para, cumpla, convenciones, estilo, puedes, avisar, redactor, principal, pegando, siguiente, página, discusión, sust, aviso, wikificar, esta, plantilla, wikificar, sust, curre. Este articulo o seccion necesita ser wikificado por favor editalo para que cumpla con las convenciones de estilo Puedes avisar al redactor principal pegando lo siguiente en su pagina de discusion sust Aviso wikificar Analisis de algoritmos Uso de esta plantilla Wikificar t sust CURRENTTIMESTAMP El analisis de algoritmos es una parte importante de la teoria de complejidad computacional que provee estimaciones teoricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado Estas estimaciones resultan ser bastante utiles en la busqueda de algoritmos eficientes A la hora de realizar un analisis teorico de algoritmos es comun calcular su complejidad en un sentido asintotico es decir para un tamano de entrada suficientemente grande La cota superior asintotica y las notaciones omega cota inferior y theta caso promedio se usan con esa finalidad Por ejemplo la busqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo en O log n coloquialmente en tiempo logaritmico Normalmente las estimaciones asintoticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen por que tener la misma eficiencia No obstante la eficiencia de dos implementaciones razonables cualesquiera de un algoritmo dado estan relacionadas por una constante multiplicativa llamada constante oculta La medida exacta no asintotica de la eficiencia a veces puede ser computada pero para ello suele hacer falta aceptar supuestos acerca de la implementacion concreta del algoritmo llamada modelo de computacion Un modelo de computacion puede definirse en terminos de un ordenador abstracto como la Maquina de Turing y o postulando que ciertas operaciones se ejecutan en una unidad de tiempo Por ejemplo si al conjunto ordenado al que aplicamos una busqueda binaria tiene n elementos y podemos garantizar que una unica busqueda binaria puede realizarse en un tiempo unitario entonces se requieren como mucho log2 N 1 unidades de tiempo para devolver una respuesta Las medidas exactas de eficiencia son utiles para quienes verdaderamente implementan y usan algoritmos porque tienen mas precision y asi les permite saber cuanto tiempo pueden suponer que tomara la ejecucion Para algunas personas como los desarrolladores de videojuegos una constante oculta puede significar la diferencia entre exito y fracaso Las estimaciones de tiempo dependen de como definamos un paso Para que el analisis tenga sentido debemos garantizar que el tiempo requerido para realizar un paso se encuentra acotado superiormente por una constante Hay que mantenerse precavido en este terreno por ejemplo algunos analisis cuentan con que la suma de dos numeros se hace en un paso Este supuesto puede no estar garantizado en ciertos contextos Si por ejemplo los numeros involucrados en la computacion pueden ser arbitrariamente grandes dejamos de poder asumir que la adicion requiere un tiempo constante usando papel y lapiz compara el tiempo que necesitas para sumar dos enteros de 2 digitos cada uno y el necesario para hacerlo con dos enteros pero de 1000 digitos cada uno Vease tambien EditarDonald Knuth AlgoritmosBibliografia EditarThomas H Cormen Charles E Leiserson Ronald L Rivest and Clifford Stein Introduction to Algorithms Second Edition MIT Press and McGraw Hill 2001 ISBN 0 262 03293 7 Chapter 1 Foundations pp 3 122 Fundamentos de algoritmia Gilles Brassard amp Paul Bratley ISBN 84 89660 00 X Datos Q333464Obtenido de https es wikipedia org w index php title Analisis de algoritmos amp oldid 137196009, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos