Técnicas de analisis de algoritmos

881 palabras 4 páginas
Técnicas de análisis de algoritmos
El método empleado en el análisis de un algoritmo depende por completo de la naturaleza del algoritmo que se trate. Por otra parte, un algoritmo puede ser analizado de distintas formas y más aún si consideramos que muchos se pueden programar iterativa o recursivamente.
Es importante identificar bien la diferencia entre el diseño del algoritmo y su análisis. Hay una gran cantidad de técnicas o ideas que se pueden utilizar al momento de crear un algoritmo para realizar alguna tarea. Por ejemplo técnicas como divide y vencerás, algoritmos golosos, combinatorios, backtracking, branch and bound, programación dinámica, algoritmos de aproximación, aleatorizados, genéticos o meméticos. Estas a su vez no deben
…ver más…
Estamos hablando aquí de su comportamiento asintótico.
Es necesario establecer cierta notación que facilite el estudio de tal comportamiento:
O (g(n)) = { f: N  N para las que existen constantes positivas c y n tales que se 0≤ f(n) ≤ cg(n) para toda n>n}
Este es el conjunto de funciones que acotan por arriba
Ω (g(n)) = { f: N  N para las que existen constantes positivas c1, c2 y N, tales que 0 ≤ cg(n) ≤ f(n) para toda n>n0}
Este es el conjunto de funciones que acotan por abajo.
Con la unión de estos conjuntos se obtiene. Θ( g(n)) = { f N  N para las que existen constantes positivas c1, c2 y n tales que 0 ≤ c1g (n) ≤ f(n)≤ c2g(n) para toda n>n0}
Estos conjuntos poseen muchas propiedades agradables en el momento de analizar un algoritmo.
Por conveniencia, se utilizan de manera indistinta expresiones como T(n) = aT(n/b) + Θ(n) alguna función del conjunto y no el conjunto en sí. De esta manera, 0(1) denota una constante.

Eficiencia de algoritmos computacionales
Medida del uso de los recursos computacionales requeridos por la ejecución de un algoritmo en función del tamaño de las entradas. T(n) Tiempo empleado para ejecutar el algoritmo con una entrada de tamaño n
Ordenes de eficiencia:
Orden lineal: Tiempo de ejecución proporcional al tamaño de la entrada.
Orden cuadrático: Aparece cuando tenemos que enumerar todas las parejas posibles de elementos de un conjunto.
Ordenes O (log n) y O (n log n): aparece en muchos

Documentos relacionados

  • Tecnicas de analisis de carteras
    1754 palabras | 8 páginas
  • Tecnicas de analisis de datos
    9284 palabras | 38 páginas
  • Técnicas de Análisis de Negocio
    4248 palabras | 17 páginas
  • Tecnicas Analisis De Texto
    934 palabras | 4 páginas
  • Tecnicas De Analisis De Inversiones
    2512 palabras | 11 páginas
  • Tecnicas De Análisis Literaio
    2959 palabras | 12 páginas
  • Tecnicas de analisis de datos
    9295 palabras | 38 páginas
  • Tecnicas de analisis instrumental
    5006 palabras | 20 páginas
  • Taller Analisis y Diseño de Algoritmos
    788 palabras | 4 páginas
  • Técnicas de análisis de cartera de inversión
    1390 palabras | 6 páginas