Analisis de los algoritmos

1. Introducción
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 componentestienen 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 o ingenieriles, nos debenpreocupar los recursos físicos necesarios para 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 confrecuencia que ambos parámetros están fijados por otras razones y se plantea la pregunta inversa: ¿Cuál es el tamaño del mayor problema que puedo resolver en T segundos y/o con M bytes de memoria? En loque sigue nos centraremos casi siempre en 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 unamedida 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 sueleutilizar 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 más importante considerar el número de arcos, dependiendo deltipo de problema a resolver); en un fichero se suele usar el número de registros, etc. Es imposible dar una regla general, pues cada problema tiene su propia lógica de coste.
Tiempo de EjecuciónUna 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ísicamente (ejecutando el programa, reloj enmano), 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; for (int i= 0; i <...