Complejidad de algoritmos, estructura de datos

INDICE

INTRODUCCION .....................................................................................................................3
COMPLEJIDAD DE ALGORITMOS..........................................................................................4
DEFINICION, FUNCIONES Y PROPIEDADES ......................................................................4
ANALISIS MEJOR, PEOR Y CASOPROMEDIO ...................................................................6
NOTACIONES ASINTOTICAS ................................................................................................8
NOTACION O ..........................................................................................................................8
NOTACION Ω......................................................................................................................................9
NOTACION Θ ....................................................................................................................................10
REGLAS BASICAS PARA LA SIMPLIFICACION Y CALCULO DE LA COMPLEJIDAD ......11
SENTENCIAS SIMPLES.......................................................................................................11
CONDICIONALES .................................................................................................................11
CICLOS ................................................................................................................................12
LLAMADAS A PROCEDIMIENTOS......................................................................................14
SECUENCIAS DE INSTRUCCIONES ...................................................................................15
CONCLUSIONES ...................................................................................................................18
BIBLIOGRAFIAS....................................................................................................................19

MEDICION DE ALGORITMOS

INTRODUCCION
En la ciencia de la computación los algoritmos son más importantes que los Lenguajes de Programacion 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, sus características son:
Independiente: Del LP y de la máquina.
Definido: De pasos claros y concretos.
Finito: En el número de pasos que usará.
Preciso: Cada paso arroja un cálculo correcto.
Recibe datos: Debe poseer datos de entrada.
Debemossaber 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 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 quetarde 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 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 ComplejidadAlgorítmica

COMPLEJIDAD DE ALGORITMOS
-DEFINICION, FUNCIONES Y PROPIEDADES
La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real.
Ambos componentes tienen su importancia, pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de...