MapaConceptal

Notación Asintotica y Clases de Eficiencia Básica

Introducción al diseño y análisis de algoritmos.

El marco de analisis de eficiencia se concentra en el orden de crecimiento de la cuenta de la operación básica de la eficiencia del algoritmo

Se usan tres notaciones

Gran Oh

Gran O Omega

Gran Theta

Propiedad útil que involucra las notaciones

Usando las definiciones formales de las notaciones asintoticas

Podemos probar sus propiedades generales

Útil para analizar algoritmos que comprenden dos partes ejecutadas consecutivamente

Uso de limites para comparar ordenes de crecimiento

Se basa en calcular el limite de la relación de dos funciones en cuestión

Tiene tres casos principales

Clases de Eficiencia básica

Denotada por

t(n) ≤ cg

para todos los

n≥no

Denotada por

t (n) ≥ cg(n)

para todos los

n ≥ no

Denotada por

c2g(n) ≤ t (n) ≤ c1g(n)

para todos los

n ≥ no

Todas funciones cuyas ordenes de crecimiento difieren en un multiplo constante

Las eficiencias de tiempo de algoritmos se dividen en

Clase 1 : Constante: El tiempo llega al infinito cuando el tamaño de entrada crece

Clase Log n: Logarirmica: Factor constante en cada iteracion del algoritmo por reducir tamaño

Clase n: Lineal: Escanean una lista de tamaños

Clase n log n: linearitmico: Divide y venceras

Clase n​​​​​​2: Cuadratica: Algoritmos con dos bucles incrustados

Clase n3: Cubica: Algoritmos con tres bucles incrustados

Clase 2n: Exponencial: Algoritmos que generan subconjuntos de conjunto de elementos

Clase n!: Factorial: Algoritmos que generan todas las permutaciones