Cuadro sinóptico II

Analisis algoritmico

Un algoritmo es un procedimiento o una serie de pasos que se deben realizar para resolver algún problema o situación. El analizar un algoritmo consiste en revisar que tan eficiente es

Trabajando con el Gran Oh

adicion de funciones

multiplicacion de funciones

La notación Big Oh

iRelaciones de dominancia

Razonamiento sobre la eficiencia

Características del diseño de algoritmos

El enfoque divide y vencerás

Clasificacion de seleccion

tipo de inserción

Coincidencia de patrones de cadenas de texto

Dividir

Conquistar

combinar

Trabajando con el Gran Oh Trabajar con la notación Big Oh, requiere hacer simplificaciones de expresiones algebraicas, las cuales se muestran en la adición y multiplicación de funciones.

La suma de dos funciones está gobernada por la dominante: O(f(n)) + O(g(n)) → O(max(f(n), g(n))) Ω(f(n)) + Ω(g(n)) → Ω(max(f(n), g(n))) Θ(f(n)) + Θ(g(n)) → Θ(max(f(n), g(n))) Esto es muy útil para simplificar expresiones

Consiste en: Dividir el problema en varios subproblemas, resolver los subproblemas recursivamente y luego combinar estas soluciones para crear una solución al problema original.

Tipo de inserción Una regla general básica en el análisis de Big Oh es que el tiempo de ejecución en el peor de los casos se deriva de multiplicar el mayor número de veces que cada ciclo anidado puede iterar.

Coincidencia de patrones de cadenas de texto La coincidencia de patrones es la operación algorítmica más fundamental en las cadenas de texto.

Combina las dos subsecuencias ordenadas para producir la respuesta ordenada.

Divide la secuencia de n elementos que se va a clasificar en dos subsecuencias de n=2 elementos cada una.

Ordena las dos subsecuencias recursivamente usando la ordenación por combinación.

Esta notación se basa en los límites superiores e inferiores simples de funciones de complejidad temporal.Con la notación Big Oh, se descartan las constantes multiplicativas. De esta manera las funciones se tratan igual

notación Big Oh

El razonamiento general sobre el tiempo de ejecución de un algoritmo suele ser fácil dada una precisa descripción escrita del algoritmo

Razonamiento sobre la eficiencia

• Funciones constantes f(n) = 1.
• Funciones logarítmicas f(n) = log n.
• Funciones lineales f(n) = n.
• Funciones superlineales f(n) = n lg n.
• Funciones cuadráticas f(n) = n2
• Funciones cúbicas f(n) = n3.
• Funciones exponenciales f(n) = cn para una constante dada c > 1
• Funciones factoriales f(n) = n!.

La notación Big Oh agrupa las funciones en un conjunto de clases que son equivalentes. Una función de crecimiento más rápido domina a una de crecimiento más lento. Cuando f y g pertenecen a diferentes clases (f(n) = Θ(g(n))), se dice que g domina f cuando f(n) = O(g(n)), a veces escrito g f algunas funciones de dominancia son:

Relaciones de dominancia

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas!Tip premium: Obten información de cómo interacciona tu audiencia:

¿Tienes una idea?

Aquí puedes incluir un dato relevante a destacar

Aquí puedes incluir un dato relevante a destacar

Se debe considerar la multiplicación por cualquier constante c > 0 O(c · f(n)) → O(f(n)) Ω(c · f(n)) → Ω(f(n)) Θ(c · f(n)) → Θ(f(n)) Cuando dos funciones en un producto son crecientes La función O(n! log n) domina n! tanto como domina log n. En general: O(f(n)) ∗ O(g(n)) → O(f(n) ∗ g(n)) Ω(f(n)) ∗ Ω(g(n)) → Ω(f(n) ∗ g(n)) Θ(f(n)) ∗ Θ(g(n)) → Θ(f(n) ∗ g(n))

Multiplicación de funciones

• Ejemplo de una clasificación de selección

Este algoritmo identifica repetidamente el elemento sin clasificar restante más pequeño y lo coloca al final de la parte ordenada de la matriz.

Clasificación de selección