Scribd
Cargar
41 vistas22 páginas

Análisis de Algoritmos y Big O

Este documento habla sobre el análisis de algoritmos y la notación Big-O. Explica conceptos como la eficiencia, la medición del tiempo de ejecución, la complejidad temporal asintótica y las reglas para definir el nivel de complejidad de un algoritmo.

Cargado por

Manuel Omar
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
41 vistas22 páginas

Análisis de Algoritmos y Big O

Este documento habla sobre el análisis de algoritmos y la notación Big-O. Explica conceptos como la eficiencia, la medición del tiempo de ejecución, la complejidad temporal asintótica y las reglas para definir el nivel de complejidad de un algoritmo.

Cargado por

Manuel Omar
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Análisis de

Algoritmos
(BigO
Notation)
Análisis de algoritmos
Si se tuvieran dos programas que hacen lo mismo, ¿cómo se podrían
comparar?

1. Eficiencia:

• Tiempo de ejecución
• Uso de espacios de memoria

2
Medición del tiempo de ejecución
• El tiempo de ejecución depende de:
1.La entrada al programa:
• Su tamaño
• Sus características
2.La calidad del código generado para el programa por el
compilador.
3.La rapidez de las instrucciones de máquina.
4.La complejidad de tiempo del algoritmo.

3
Notación asintótica – Big O

• Complejidad temporal (y espacial): Tiempo (o espacio) requerido por un


algoritmo, expresado con base en una función que depende del tamaño
del problema.

• Complejidad temporal asintótica (y espacial): Comportamiento límite


conforme el tamaño del problema se incrementa. Determina el tamaño
del problema que puede ser resuelto por un algoritmo.

4
5
Reglas
• Reglas para definir el nivel de complejidad de un algotimo
1. Instruciones secuenciales
2. Condiciones ( if’s )
3. Ciclos ( for y/o while)
• Ciclos Anidados
4. Recursividad
1-Secuencial
• Se selecciona la que impacta con mayor fuerza a la secuencia
de instrucciones (que tenga un orden mayor)
2-Condicional
• Cuando tenemos if- else se escoge la de orden mayor.
• Si solo tenemos if se escoge el orden de la condicional.
3-Ciclos
• Si el rango de repetición está
en términos de n, el orden
será:
• Lineal: cuando a la VCC se
le suma o resta
• Logarítmico: cuando a la
VCC divide o multiplica
• Ciclos anidados se multiplican
los órdenes.
Ejemplos
== ==
Ciclos anidados
4-Recursividad
Ejemplos
Planteamiento de fórmulas de
recurrencia
Usadas para comprobar la eficiencia de los algoritmos recursivos
1. Poner el tiempo de ejecución en términos T(n)
2. Igualar T(n) a la cantidad de llamadas recursivas (en términos
de su parámetro de control)
3. Igualar el tiempo requerido del caso base en función del
número de operaciones básicas que requiere su proceso
Ejemplo factorial
FÓRMULA DE RECURRENCIA

Solo toma una


operación

Caso base

Parámetro de control
Tiempo que toma el
factorial para n-1
Dado el algoritmo ¿cuál es la fórmula
recursiva o de recurrencia?
CASO BASE: operación
aritmética (la que sea)

PARTE RECURSIVA: : 3 llamadas recursivas


de la mitad de n

FÓRMULA DE RECURRENCIA

También podría gustarte