O grande, omega grande y notacion asintotica
Páginas: 2 (263 palabras)
Publicado: 12 de octubre de 2010
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.
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.
Leer documento completo
Regístrate para leer el documento completo.