Teoria de la complejidad algoritmica

3452 palabras 14 páginas
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

Documentos relacionados

  • Maquina Turing Suma Binarios
    2427 palabras | 10 páginas
  • Proyecto productivo papeleria
    598 palabras | 3 páginas
  • Clasificacion De Los Tipos De Datos E Informacion
    767 palabras | 4 páginas
  • Arquitectura Liquida
    3518 palabras | 15 páginas
  • Costo de capital
    3610 palabras | 15 páginas
  • Evolucion y Desarrollo Del Sistema Nervioso
    3426 palabras | 14 páginas
  • Calderas pirotubulares
    859 palabras | 4 páginas
  • Encriptacion de textos
    1804 palabras | 8 páginas
  • POO 400 preguntas
    9169 palabras | 37 páginas
  • Informatica
    2255 palabras | 10 páginas