Complejidad Algoritmica

2.1. Complejidad de un algoritmo. En el desarrollo de un programa computacional resulta necesario definir criterios para medir su rendimiento o comportamiento. Estos criterios se centran principalmente en su simplicidad y en el uso eficiente de los recursos. Respecto al uso eficiente de los recursos, éste suele medirse en función de dos parámetros: el espacio, es decir, memoria que utiliza, y eltiempo, lo que tarda en ejecutarse. Ambos representan los costes que supone encontrar la solución al problema planteado mediante un algoritmo. Dichos parámetros van a servir además para comparar algoritmos entre sí, permitiendo determinar el más adecuado de entre varios que solucionan un mismo problema. En esta sección nos referiremos exclusivamente a la eficiencia temporal. El análisis de laeficiencia temporal de los algoritmos consta de dos fases: análisis a priori y análisis a posteriori. El análisis a posteriori ofrece una medida real, consistente en medir el tiempo de ejecución del algoritmo para unos valores de entrada dados y en un ordenador concreto. El análisis a priori proporciona una medida teórica, que consiste en obtener una función que acote (por arriba o por abajo) eltiempo de ejecución del algoritmo para unos valores de entrada dados. Esta medida ofrece estimaciones del comportamiento de los algoritmos de forma independiente del ordenador en donde serán implementados y sin necesidad de ejecutarlos. La unidad de tiempo a la que debe hacer referencia esta medida de eficiencia temporal no puede ser expresada en segundos o en otra unidad de tiempo concreta, pues noexiste un ordenador estándar al que puedan hacer referencia todas las medidas. Esta medida de eficiencia temporal se define como una función del tamaño o talla de la entrada. Definición 2.1.1. Se denomina tamaño de la entrada el número de componentes sobre los que se va a ejecutar el algoritmo. Por ejemplo, la dimensión del vector a ordenar o el tamaño de las matrices a multiplicar. En el caso dealgoritmos que resuelvan determinado problema sobre grafos el tamaño de la entrada podría ser el número de vértices o el número de aristas. Denotaremos por T(n) el tiempo de ejecución de un algoritmo para una entrada de tamaño n, donde T(n) indica el número de instrucciones ejecutadas por un ordenador idealizado. Principio de Invarianza. Dado un algoritmo y dos implementaciones suyas I1 e I2, quetardan T1(n) y T2(n) segundos respectivamente, existe una constante real c > 0 y un número natural n0 tales que para todo n ≥ n0 se verifica que T1 (n) ≤ T2 (n) . Es decir, el tiempo de ejecución de dos implementaciones distintas de un algoritmo dado, ya sea del mismo código ejecutado por dos máquinas de distinta velocidad, como de dos códigos diferentes que implementen el mismo método, no va adiferir más que en una constante multiplicativa. Definición 2.1.2. Se dice que un algoritmo tarda un tiempo del orden de T(n) si existen

una constante real c > 0 y una implementación I del algoritmo que tarda menos que cT(n), para todo n tamaño de la entrada. El comportamiento de un algoritmo puede cambiar notablemente para diferentes entradas pues para muchos programas el tiempo de ejecución esen realidad una función de la entrada específica, y no sólo del tamaño de ésta. Así suelen estudiarse tres casos para un mismo algoritmo: caso peor, caso mejor y caso medio. El caso mejor corresponde a la traza (secuencia de sentencias) del algoritmo que realiza menos instrucciones. Análogamente, el caso peor corresponde a la traza del algoritmo que realiza más instrucciones, lo cual nos aseguraque al menos el algoritmo se desempeñará de esa forma . Respecto al caso medio, corresponde a la traza del algoritmo que realiza un número de instrucciones igual a la esperanza matemática de la variable aleatoria definida por todas las posibles trazas del algoritmo para un tamaño de la entrada dado, con las probabilidades de que éstas ocurran para esa entrada. Esta es la medida más difícil de...