O grande, omega grande y notacion asintotica

Solo disponible en BuenasTareas
  • Páginas : 2 (263 palabras )
  • Descarga(s) : 0
  • Publicado : 12 de octubre de 2010
Leer documento completo
Vista previa del texto
Tarea No. 2 Fecha de elaboración: 8 / Octubre / 10

Nombre del alumno: Daniel Andrés Lomelí Gómez

Asignatura y Sección: Análisis y Diseño de Algoritmos,D02

“Definición de O grande, Omega grande y Notación asintótica”

Notación O-grande

Da una cota superior de la forma en que crece el tiempo deejecución.

En general, el tiempo de ejecución es proporcional, esto es, multiplica por una constante a alguno de los tiempos de ejecución anteriormentepropuestos, además de la suma de algunos términos más pequeños. La notación O-grande ignora los factores constantes, es decir, ignora si se hace una mejor o peorimplementación del algoritmo, además de ser independiente de los datos de entrada del algoritmo. Es decir, la utilidad de aplicar esta notación a un algoritmo esencontrar un límite superior del tiempo de ejecución, es decir, el peor caso.

DEFINICIÓN:

Dada una función f:N→R+, llamamos orden de f al conjunto de todaslas funciones de N en R+ acotadas superiormente por un múltiplo real positivo de f para valores de n suficientemente grandes.
Se denota O(f), y será:O(f)={t: N→R+ / (c(R+, (n0(N, ( n>=n0 : t(n)=n0 : t(n)>=cf(n)}

Notación Asintótica

Se utilizan para estudiar tiempos de ejecución u ocupaciones dememoria.
Representan la forma en que crece una función.
En general no consideran constantes, que no son valores propios de los algoritmos.
Son asintóticas puesrepresentan el comportamiento cuando el tamaño de la entrada tiende a infinito, pues para valores grandes es cuando puede haber problemas de tiempo o memoria.
tracking img