Estructura de datos

Analisis de Algoritmos 1
1. Conceptos de Complejidad de Algoritmos 2
2. Aritmetica de la notación O 3
3. Complejidad 3
1. Tiempo de Ejecucion 4
2. Complejidad del Espacio 4
4. Selección de Algoritmo 4
2. Manejo de Memoria 4
1. Memoria Estatica 5
2.Memoria Dinamica 5
Ejercicios 6

UNIDAD I. ANALISIS DE ALGORITMOS

Un análisis de algoritmos se basa en las características estructurales del algoritmo que respalda al programa y en la cantidad de memoria que este utiliza para resolver un problema.

Además es un mediopor el cual podemos evaluar el diseño de las estructuras de datos de dicho programa midiendo así su eficiencia con el cual es capaz de resolver el problema planteado.

- ¿Qué es un algoritmo?

Una definición informal (no se considera aquí una definición formal, aunque existe): conjunto finito de reglas que dan una secuencia de operaciones para resolver todos los problemas de un tipo dado. Deforma más sencilla, podemos decir que un algoritmo es un conjunto de pasos que nos permite obtener un dato. Además debe cumplir estas condiciones:

  · Finitud: el algoritmo debe acabar tras un número finito de pasos. Es más, es casi fundamental que sea en un número razonable de pasos.

  · Definibilidad: el algoritmo debe definirse de forma precisa para cada paso, es decir, hay que evitartoda ambigüedad al definir cada paso. Puesto que el lenguaje humano es impreciso, los algoritmos se expresan mediante un lenguaje formal, ya sea matemático o de programación para un computador.

  · Entrada: el algoritmo tendrá cero o más entradas, es decir, cantidades dadas antes de empezar el algoritmo. Estas cantidades pertenecen además a conjuntos especificados de objetos. Por ejemplo, puedenser cadenas de caracteres, enteros, naturales, fraccionarios, etc. Se trata siempre de cantidades representativas del mundo real expresadas de tal forma que sean aptas para su interpretación por el computador.

 · Salida: el algoritmo tiene una o más salidas, en relación con las entradas.

 · Efectividad: se entiende por esto que una persona sea capaz de realizar el algoritmo de modo exacto ysin ayuda de una máquina en un lapso de tiempo finito.

- Clasificación de algoritmos

  * Algoritmo determinista: en cada paso del algoritmo se determina de forma única el siguiente paso.

  * Algoritmo no determinista: deben decidir en cada paso de la ejecución entre varias alternativas y agotarlas todas antes de encontrar la solución.

Todo algoritmo tiene una serie de características,entre otras que requiere una serie de recursos, algo que es fundamental considerar a la hora de implementarlos en una máquina.

Estos recursos son principalmente:

 · El tiempo: período transcurrido entre el inicio y la finalización del algoritmo.
 · La memoria: la cantidad (la medida varía según la máquina) que necesita el algoritmo para su ejecución.

En general, la mayoría de losproblemas tienen un parámetro de entrada que es el número de datos que hay que tratar, esto es, N. La cantidad de recursos del algoritmo es tratada como una función de N. De esta manera puede establecerse un tiempo de ejecución del algoritmo que suele ser proporcional a una de las siguientes funciones:

• 1 : Tiempo de ejecución constante. Significa que la mayoría de las instrucciones se ejecutanuna vez o muy pocas.

• logN : Tiempo de ejecución logarítmico. Se puede considerar como una gran constante. La base del logaritmo (en informática la más común es la base 2) cambia la constante, pero no demasiado. El programa es más lento cuanto más crezca N, pero es inapreciable, pues logN no se duplica hasta que N llegue a N2.

• N : Tiempo de ejecución lineal. Un caso en el que N...