Notacion asintota Omega grande

La función omega grande se utiliza para especificar una cota inferior para la velocidad de crecimiento de una función f(n) cuando esta en función de n. Y se usa la notación T(n) es Ω(g(n)) se lee: T(n) es omega grande de g(n) y significa que existe una constante C tal que T(n) ≥ c(g(n)) para un numero infinito de valores de n.

Ejemplo 1: - programa 6
Verificar la funcion , c=1 para todos los valores n >=0

Programa-7….

para n>=0 y c=1/100

Programa-8….
T(n)=n, para n>=1 impar y c=1

Aritmetica de la notacion O

Notación asintótica O grande

Se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una función. La utilidad de aplicar esta notación a un algoritmo es encontrar el limite superior del tiempo de ejecución, es decir el peor caso.

, para todo

Esto significa que la función g(n) pertenece o es valida para f(n) si solo si existen las constantes c y n0, tales que para

Nota: el orden de magnitud de la función será el orden del término de la función mas grande respecto de n.

(PROGRAMA 3)

Ejemplo 1: Supóngase que

cuando n0 = 1 y c =4, n >=1.

Verifique la función utilizando la O grande:

PROGRAMA 4:

cuando n0=0, c=5 para .

PROGRAMA 5:

cuando n0 = 0, c=50 para .

Temario

Materia: Estructura de Datos

Serie: 3w3A

Teacher: MC Luz Elena Cortez Galvan

Temario

Unidad 1 - Analisis de Algoritmos

Unidad 2 - Manejo de memoria

Unidad 3 - Estructuras Lineales Estaticas y Dinamicas ( pilas, colas, listas)

Unidad 4 - Recursividad

Unidad 5 - Estructuras no Lineales Estaticas y Dinamicas (Arboles)

Unidad 6 - Ordenacion Interna (Burbuja, Shell, Quicksort, Radix)

Unidad 7 - Ordenacion Externa (intercalacion simple, cuadratica, merge )

Unidad 8 - Metodos de Busqueda (secuencial, binaria, hash)

Evaluacion: 80% Examen (teoria/practica)

15% Programas

5% Asistencia/Participacion

____

100%

====