Análisis de algoritmos no recursivos

El análisis de complejidad de los algoritmos no recursivos (iterativos) se realiza bajo los principios del peor caso y generalmente devolverá la cota superior ajustada del orden de este (O).

En principio se considera válido cuando solo se desea obtener una cota para valores grandes de n, basándose en que se cumple el principio de invarianza del análisis asintótico.

Para los algoritmos iterativos es únicamente necesario conocer los órdenes de complejidad O de las tres estructuras de control que todo algoritmo iterativo puede emplear.

La notación de Landau (O)

Se dice que la función 𝑓(𝑛) “es de orden O 𝑔(𝑛)” [O(g(n))], si existen constantes positivas 𝑐 y 𝑛0 tales que |𝑓 𝑛 | ≤ 𝑐 |𝑔 𝑛 | cuando 𝑛 ≥ 𝑛0

Ejemplos:

n+5 es O(n) pues n+5 ≤ 2n para toda n ≥ 5
(n+1) 2 es O(n2 ) pues (n+1) 2 ≤ 4n 2 para n≥ 1
(n+1) 2 NO es O(n) pues para cualquier c > 1 no se cumple que (n+1) 2 ≤ c*n

La notación O

La notación O proporciona una cota superior para la tasa de crecimiento de una función

La siguiente tabla muestra la relación asintótica de la notación de orden O.

Principio de invarianza del análisis asintótico

Cambios en el entorno HW o SW afectan a factores constantes pero no al orden de complejidad O(f(n))

El análisis de la eficiencia es asintótico → sólo es válido para tamaños de problema suficientemente grandes lo que hace valido el principio de invarianza.

“Dos implementaciones de un mismo algoritmo no diferirán más que en una constante multiplicativa”

Si f1 (n) y f2 (n) son los tiempos consumidos por dos implementaciones de un mismo algoritmo, se verifica que:

Reglas práctica del análisis de algoritmos

Operaciones primitivas.

Tienen complejidad constante O(1)

Secuencia de instrucciones

Máximo de la complejidad de cada instrucción (regla de la suma).

Condiciones simples

Operaciones necesarias para evaluar la condición más las requeridas para ejecutar la consecuencia (peor caso).

Condiciones alternativas

Operaciones necesarias para evaluar la condición más las operaciones requeridas para ejecutar el mayor número de operaciones de las consecuencias (peor caso).

Bucle con iteraciones fijas

Multiplicar el número de iteraciones por la complejidad del cuerpo (regla del producto).

Bucle con iteraciones variables

Igual pero poniéndose en el peor caso (ejecutar el mayor número de iteraciones posible).

Llamadas a subprogramas

funciones o métodos: Operaciones de asignación de cada parámetro más las operaciones de ejecución del cuerpo, más el número de operaciones del retorno.

Ordenes más comunes de los algoritmos

Comportamiento de las funciones

Análisis por bloques

El análisis de complejidad por bloques proporciona un importante medio para hacer un análisis más dinámico, que se basa principalmente en el conocimiento del orden de los bloques de instrucciones.

Un bloque de instrucciones puede ser un algoritmo del cual conocemos su complejidad computacional. Para determinar el orden de un bloque, es necesario tener en mente el orden de las estructuras de control más usuales.

El análisis por bloques implica el análisis de:

1. Secuencias de instrucciones

2. Condicionales

3. Ciclos

Regla 1. Secuencia de Instrucciones

Regla 2. Decisiones

Regla 3. Ciclos

Consideraciones especiales

En decisiones y ciclos anidados

Analizar el código desde la intrucción más interna hacia la más externa

Tips para los ciclos:

¿"Normalmente" cuál es el orden de la instrucción interna?

Si la variable de control se incrementa o decrementa con un valor constante: Orden LINEAL
Si la variable de control se multiplica o divide por un valor constante: Orden LOGARITMICO