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%

====

Analisis de algoritmos

1.1 Concepto de complejidad de algoritmos
**Teoria de la complejidad computacional:
Es la parte de la teoria de la computacion que estudia los recursos necesarios durante el calculo para resolver un problema.
Estos recursos son:
- Tiempo
- Espacio

== clases de complejidad ==
Los problemas de decisión (aquellos donde la respuesta posible es si o no)
se clasifican en conjuntos de complejidad comparables que son llamados clases de complejidad.

A) Clase de complejidad P.
Es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinomico por una maquina de Turing , lo que corresponde a problemas que pueden ser resueltos aun en el peor de sus casos

Ejemplo:
• Saber si un numero es primo o no (programa 1)
• Decidir si una frase pertenece a un conjunto dado de frases

B) Clase de complejidad NP.
Es el conjunto de los problemas de decisión que puedes ser resueltos por una maquina de Turing no determinista en tiempo polinomico. Los problemas de esta clase tienen la propiedad de que su solucion puede ser verificada.

Ejemplo
• El problema del agente viajero. (programa 2)
• El problema de satisfaccionalidad booleana.

C) Clase de complejidad NP-Completo.
Es el subconjunto de los problemas de decisión en NP que se destacan por su extrema complejidad en la cual algunos de ellos en la actualidad no han encontrado una solucion satisfactoria.

Ejemplo
• La suma de subconjuntos dado un conjunto de 5 enteros ¿existe un subconjunto no vacio cuyos elementos sea 0?
• ¿dos grafos son isomorfos y se pueden transformar uno en el otro simplemente renombrando sus vértices?


Diagrama de relación entre las clases de complejidad













Pregunta ¿ las clases P y NP son diferentes?
El clan mathematics institut ofrece un millon de doles a quien sea ca[az de responder satisfactoriamente a esa pregunta!