Estimacion

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.

REGLA DE LA SUMA ...................................................................................................8

2.

REGLA DEL PRODUCTO.............................................................................................8

IMPORTANCIA DE LA EFICIENCIA .................................................................................9
ESTIMACIÓN DE LA COMPLEJIDAD EN ALGORITMOS NO RECURSIVOS ...........10
EJERCICIOS DE APLICACIÓN .........................................................................................15OBJETIVOS:.........................................................................................................................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ás importantes que los LP1 o que las
computadoras; la solución de un problemahaciendo 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, sus caracterí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 que entregan la solución, existen muchas alternativas de solución yestas 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 simple
vista con sólo observar la cantidad de líneas delprograma, 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

Ing. Rolf Pinto López

3

Algoritmos y Estructura de Datos I

Ing. Rolf Pinto López

COMPLEJIDADALGORÍ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 algún programa.
2. Complejidad Espacial:...