Analisis de algoritmos

ÍNDICE p g.

INTRODUCCIÓN 3

UNIDAD 1 ANÁLISIS DE ALGORITMOS

1. CONCEPTO DE COMPLEJIDAD DE ALGORITMOS………... 4

2. ARITMÉTICA DE LA NOTACIÓN O……… ……..…………. …6

1. COMPLEJIDAD ………………………………………………...……..7

1.3.1 TIEMPO DE EJECUCIÓN DE UN ALGORITMO…… …….…81.3.2 COMPLEJIDAD EN ESPACIO………………………….. ….….……9

1.4 SELECCIÓN DE UN ALGORITMO……………………….…..………10

UNIDAD 2 MANEJO DE MEMORIA

2.1 MANEJO DE MEMORIA ESTÁTICA……………………..…….…….12

2.2 MANEJO DE MEMORIA DINÁMICA………………….….….........13

BIBLIOGRAFIA… …… …...…………………… … .…..15

INTRODUCCIÓN

La resolución práctica de un problema exige por una parte un algoritmo o método deresolució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 anécdota.
A efectos prácticos, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute. Aunque puede haber muchos parámetros, los másusuales son el tiempo de ejecución y la cantidad de memoria (espacio). Ocurre con frecuencia que ambos parámetros están fijados por otras razones y se plantea la pregunta inversa: ¿cual es el tamaño del mayor problema que puedo resolver en T segundos y/o con M bytes de memoria? En lo que sigue nos centraremos casi siempre en el parámetro tiempo de ejecución, si bien las ideas desarrolladas sonfácilmente aplicables a otro tipo de recursos.
El concepto exacto que mide N depende de la naturaleza del problema. Así, para un vector se suele utilizar como N su longitud; para una matriz, el número de elementos que la componen; para un grafo, puede ser el número de nodos (a veces es mas importante considerar el número de arcos, dependiendo del tipo de problema a resolver). Es imposible dar una reglageneral, pues cada problema tiene su propia lógica de coste.

UNIDAD 1 ANÁLISIS DE ALGORITMOS

1. CONCEPTO DE COMPLEJIDAD DE ALGORITMOS

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:Complejidad Temporal o Tiempo de ejecución: Tiempo de cómputo necesario para ejecutar algún programa.

Complejidad Espacial: Memoria que utiliza un programa para su ejecución, La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoriaestática de un algoritmo se suma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.

Este análisis se basa en las Complejidades Temporales, con este fin, para cada problema determinaremos una medida N, que llamaremos tamaño de la entrada o número de datos a procesarpor el programa, intentaremos hallar respuestas en función de dicha N.
El concepto exacto que cuantifica N dependerá de la naturaleza del problema, si hablamos de un array se puede ver a N como el rango del array, para una matriz, el número de elementos que la componen; para un grafo, podría ser el número de nodos o arcos que lo arman, no se puede establecer una regla para N, pues cada problemaacarrea su propia lógica y complejidad

Para cada problema determinaremos una medida N de su tamaño (por número de datos) e intentaremos hallar respuestas en función de dicho N.
El concepto exacto que mide N depende de la naturaleza del problema.
Así, para un vector se suele atizar como N su longitud; para una matriz, el número de elementos que la componen; para un grafo, puede ser el número...