MapaConceptal

Nodos de los diagramas

• 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

• Tres (binary/octet-stream)

• 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