Teoria de la complejidad algoritmica

Algoritmos y Estructura de Datos I

Ing. Rolf Pinto López

Algoritmos y Estructura de Datos I

Ing. Rolf Pinto López

1

Algoritmos y Estructura de Datos I

Ing. Rolf Pinto López

TEORÍA DE LA COMPLEJIDAD ALGORÍTMICA ............................................................3 INTRODUCCIÓN...................................................................................................................3 COMPLEJIDAD ALGORÍTMICA ........................................................................................4 Tiempo de Ejecución ...............................................................................................................4 Asintotas..................................................................................................................................5 Órdenes de Complejidad .........................................................................................................6 Reglas de la Notación Asintótica ............................................................................................8 1. 2. Regla de la suma..............................................................................................................8 Regla del producto ...........................................................................................................8

IMPORTANCIA DE LA EFICIENCIA .................................................................................9 ESTIMACIÓN DE LA COMPLEJIDAD EN ALGORITMOS NO RECURSIVOS ...........10 Ejercicios de aplicación.........................................................................................................15 Objetivos: ..............................................................................................................................15

Ing. Rolf Pinto López

2

Algoritmos y Estructura de Datos I

Ing. Rolf Pinto López

TEORÍA DE LA COMPLEJIDAD ALGORÍTMICA

INTRODUCCIÓN En la ciencia de la computación los algoritmos son másimportantes que los LP1 o que las computadoras; la solución de un problema haciendo uso de las computadoras requiere por una parte un algoritmo o método de resolución y por otra un programa o codificación del algoritmo en un LP. Ambos componentes tienen importancia; pero la del algoritmo es absolutamente indispensable; sabemos que un algoritmo es una secuencia de pasos para resolver un problema, suscaracterísticas son: 1. Independiente: Del LP y de la máquina. 2. Definido: De pasos claros y concretos. 3. Finito: En el número de pasos que usará. 4. Preciso: Cada paso arroja un cálculo correcto. 5. Recibe datos: Debe poseer datos de entrada. 6. Arroja información: Debe arrojar información de salida. Debemos saber que una solución es un conjunto único, pero no es el único conjunto de pasos queentregan la solución, existen muchas alternativas de solución y estas alternativas pueden diferir por: Número de pasos Estructuras Ahora que sabemos que existen muchas alternativas de solución para un problema, debemos seleccionar el algoritmo más eficiente, el mejor conjunto de pasos, el que tarde menos en ejecutarse, que tenga menos líneas de código. Esta selección puede ser ejecutada a simplevista con sólo observar la cantidad de líneas del programa, pero cuando el programa crece se requiere una medición más exacta y apropiada, para esto se realizan ciertas operaciones matemáticas que establecen la eficiencia teórica del programa, al estudio de estos casos se denomina Complejidad Algorítmica.

1

Lenguajes de Programación 3

Ing. Rolf Pinto López

Algoritmos y Estructura deDatos I

Ing. Rolf Pinto López

COMPLEJIDAD ALGORÍTMICA Un algoritmo será mas eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo. La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad: 1. Complejidad Temporal o Tiempo de ejecución: Tiempo de cómputo necesario para ejecutar...