Procesos De Evaluacion Del Desempeño

[pic]

Trabajo Unidad I:

Análisis de Algoritmos

Materia:

Estructura de Datos

Alumno:

Fecha Entrega:

ANÁLISIS DE ALGORITMOS

Complejidad.

Introducción.

La resoluciónprá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 delalgoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.

A efectos prácticos o ingenieriles, nos deben preocupar los recursos físicos necesariospara que un programa se ejecute. Aunque puede haber muchos parámetros, los más usuales son el tiempo de ejecución y la cantidad de memoria (espacio). Ocurre con frecuencia que ambos parámetros estánfijados 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 siempreen el parámetro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.
Para cada problema determinaremos una medida N de su tamaño e intentaremoshallar 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 utilizar como N su longitud; para una matriz, el número deelementos que la componen; para un grafo, puede ser el número de nodos, en un fichero se suele usar el número de registros, etc. Es imposible dar una regla general, pues cada problema tiene su propialógica de coste.

Tiempo de Ejecución.
Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denominaremos T(N). Esta función se puede medir físicamenteejecutando el programa, o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción. Así, un trozo sencillo de programa como
S1;...