Complejidad de Algoritmos

COMPLEJIDAD DE ALGORITMOS
Un programa es una representación de un algoritmo en un lenguaje de programación que
puede ser interpretado y ejecutado en una computadora. Existen muchas formas derepresentar un
algoritmo en un programa, al igual que soluciones. La cuestión es ¿cuál es el mejor algoritmo para
resolver un problema?. Una posible alternativa para medir dos algoritmos consiste enrepresentar
ambos en un mismo lenguaje y ejecutarlos en un mismo computador; a continuación medir el
tiempo requerido por cada uno de ellos para obtener la solución.
El tiempo de ejecución es uno de losparámetros importantes para medir la eficiencia de un
algoritmo. El tiempo real requerido para ejecutar un algoritmo es directamente proporcional al
número de operaciones básicas que se debenejecutar. Por lo tanto, medir el tiempo real es como
medir el núm. de operaciones elementales (aritméticas, comparaciones, sentencias, etc.). Por lo
que, para análisis se llamar tiempo de ejecución alnúm. de operaciones elementales realizadas, y
no al tiempo físico. Para ejemplificar la complejidad el parámetro que usa mejor el tiempo. Si
medimos el tiempo nos encotramos que al no tener una únicamanera de representar un algoritmo,
ni haber un solo tipo de computador, la medida que obtengamos será una variable dependiente de el
lenguaje de programación, el programa que representará alalgoritmo (hábitos, estilo y vicios de
programador) y el que lo ejecuta por lo que es necesario medir el tiempo requerido por un
algoritmo independientemente de su representación y del computador que loejecute.
El espacio que ocupa un algoritmo en cuanto a recursos utilizados (memoria, almacenamiento
externo, etc.).
Otro factor a considerar la cantidad de datos que el algoritmo va a manejar, ya queal ir aumentando
los recursos requeridos pueden aumentar extraordinariamente.
Por las razones anteriores, generalmente se emplean funciones que describen el comportamiento de
un algoritmo en...