Complejidad de algoritmos

1 Introducción

Un objetivo natural en el desarrollo de un programa computacional es mantener tan bajo como sea posible el consumo de los diversos recursos, aprovechándolos de la mejor manera que se encuentre. Se desea un buen uso, eficiente, de los recursos disponibles, sin desperdiciarlos.
Para que un programa sea practico, en términos de requerimientos de almacenamiento y tiempo deejecución, debe organizar sus datos en una forma que apoye el procesamiento eficiente.
Siempre que se trata de resolver un problema, puede interesar considerar distintos algoritmos, con el fin de utilizar el más eficiente. Pero, ¿cómo determinar el cual es “el mejor”?. La estrategia empírica consiste en programar los algoritmos y ejecutarlos en un computador sobre algunos ejemplares de prueba. Laestrategia teórica consiste en determinar matemáticamente la cantidad de recursos (tiempo, espacio, etc.) que necesitara el algoritmo en función del tamaño del ejemplar considerando.
El tamaño de un ejemplar x corresponde formalmente el número de dígitos binarios necesarios para representarlo en el computador. Pero a nivel algorítmico consideraremos el tamaño como el número de elementos lógicoscontenidos en el ejemplar.
Generalmente hay dos metas en el diseño de programas de cómputo:
* El diseño de un algoritmo que sea fácil de entender, codificar y depurar (ingeniería de software).
* El diseño de un algoritmo que haga uso eficiente de los recursos de la computadora (análisis y diseño de algoritmo).
El análisis de algoritmo nos permite medir la dificultad inherente de un problema yevaluar la eficiencia de un algoritmo.
Concepto de Eficiencia

Un algoritmo es eficiente cuando logra llegar a sus objetivos planteados utilizando la menor cantidad de recursos posibles, es decir, minimizando el uso de memoria, de pesos y de esfuerzo humano.
Un algoritmo es eficaz cuando alcanza el objetivo primordial, el analisis de resolución del problema se lo realiza prioritariamente.Puede darse el caso de que exista un algoritmo eficaz pero no eficiente, en lo posible debemos de manejar estos dos conceptos conjuntamente.
La eficiencia de un programa tiene dos ingredientes fundamentales: Espacio y tiempo.
* La eficiencia en espacio es una medida de la cantidad de memoria requerida por un programa.
* La eficiencia en tiempo se mide en términos de la cantidad de tiempo deejecución del programa.
Ambas dependen del tipo de computador y compilador, por lo que no se estudiara aquí la eficiencia de los programas, sino la eficiencia de los algoritmos. Asimismo, este analices dependerá de si trabajamos con máquinas de un solo procesador o de varios de ellos. Centrémonos nuestra atención en los algoritmos para máquinas de un solo procesador que ejecutan una instruccióny luego otra.
Medidas de Eficiencia

Inventar algoritmos es relativamente fácil. En la práctica, sin embargo, no se pretende sólo diseñar algoritmos, sino más bien que buenos algoritmos.
Así, el objetivo es inventar algoritmos y probar que ellos mismos son buenos.
La calidad de un algoritmo puede ser avalada utilizando varios criterios. Uno de los criterios más importanteses el tiempo utilizado en la ejecución de los algoritmos. Existen varios aspectos a considerar en cada criterio de tiempo. Uno de ellos está relacionado con el tiempo de ejecución requerido por los diferentes algoritmos, para encontrar la solución final de un problema o cálculo particular.
Normalmente, un problema se puede resolver por métodos distintos, condiferentes grados de eficiencia. Por ejemplo: búsqueda de un número en una guía telefónica.
Cuando se usa un computador es importante limitar el consumo de recursos.
Recursos de Tiempo
* Aplicaciones informáticas que trabajan “en tiempo real” requieren que los cálculos se realicen el menor tiempo posible.
* Aplicaciones que manejan un gran volumen de información si...