Algoritmos y Estructura de Datos I

Ing. Rolf Pinto López

Algoritmos y Estructura de Datos I

Ing. Rolf Pinto López

1

Algoritmos y Estructura de Datos I

Ing. Rolf Pinto López

TEORÍA DE LA COMPLEJIDAD ALGORÍTMICA ............................................................3 INTRODUCCIÓN ...................................................................................................................3 COMPLEJIDAD ALGORÍTMICA ........................................................................................4 Tiempo de Ejecución ...............................................................................................................4 Asintotas …ver más…

Para calcular la memoria está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 procesar por 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 problema acarrea su propia lógica y complejidad. TIEMPO DE EJECUCIÓN El tiempo de Ejecución de un programa se mide en función de N, lo que designaremos como T(N). Esta función se puede calcular físicamente ejecutando el programa acompañados de un reloj, o calcularse directamente sobre el código, contando las instrucciones a ser ejecutadas y multiplicando por el tiempo requerido por cada instrucción. Así, un trozo sencillo de código como:
S1; for(x = 0; x < N; x++) S2;

Demanda: T(N) = t1 + t2