Análisis de complejidad

Introducción a la notación Big-O

http://discrete.gr/complexity/?es

Introducción

• La complejidad de un algoritmo es una forma de evaluar qué tan rápido se ejecuta un algoritmo o programa.

• El análisis de complejidad permite comparar dos algoritmos, de manera independiente de su implementación y nos permite explicar cómo se comporta a medida que aumentan los datos de entrada.

Introducción

• Para analizar el comportamiento de un algoritmo debemos contar cuántas instrucciones fundamentales ejecuta el pedazo de código que estamos analizando.

• Para contar cuántas instrucciones hay, tenemos que encontrar las instrucciones sencillas que pueden ser ejecutados directamente por la UCP

Instrucciones básicas

• Supondremos que nuestro procesador puede ejecutar las siguientes instrucciones por separado.

• Asignar un valor a una variable• Buscar el valor de un elemento particular de un

arreglo• Comparar dos valores• Incrementar un valor• Operaciones aritméticas básicas

Analicemos este fragmento de código

int M = A[0]for (int i=0; i<n;i++) { if (A[i] >= M) { M = A[i]; }}

Buscar, asignar = 2 instrucciones

1ª iteración: asignación y comparación =2 instruccionesSig. “n” iteraciones: comparación e incremento=2 instrucciones

Buscar y comparar = 2 instrucciones

Si entra al if: encontrar y asignar = 2 instrucciones *pero no siempre ocurre*

El ciclo for sin ninguna instrucción tiene f(n) = 4 + 2*n instrucciones.La cantidad de instrucciones con el if no pueden definirse tan fácilmente

Análisis del peor caso

• f(n) no puede definirse tan fácilmente por que la cantidad de instrucciones no sólo depende de “n” sino también de la entrada.

• Si A=[1,2,3,4]• Si A=[4,3,2,1]• ¿Qué es lo peor que puede ocurrir con

nuestro algoritmo? ¿Cuándo se requerirá la mayor cantidad de instrucciones?

Análisis del peor caso

• En el ejemplo, el peor caso es cuando M tiene que reemplazarse cada vez, y genera la mayor cantidad de instrucciones en el for.

• f(n)=4 + 2n + 4n =6n+4• Esta función f, dado un tamaño “n” del

problema, entrega el número de instrucciones que serán necesarias en el peor de los casos.

Comportamiento asintótico

• No siempre es necesario contar las instrucciones, además de que la cantidad real de instrucciones depende del compilador y el lenguaje de programación.

• Ahora encontraremos la función “f” a través de un filtro.

Comportamiento asintótico

• En la función 6n + 4 tienen 2 términos: 6n y 4• Queremos ver cómo se comporta el algoritmo

cuando se le trata de forma ruda (peor escenario) lo cual es bastante útil cuando comparamos algoritmos.

• De los términos de la función vamos a ignorar los que crecen lentamente y mantendremos los que crecen rápidamente conforme “n” se incrementa.

Comportamiento asintótico

• En nuestra función dejaremos el término 6n.• También ignoraremos a la constante que

multiplica a “n”. f(n)=n• Esto de eliminar los factores y mantener el

término de mayor crecimiento, es lo que denominamos “comportamiento asintótico”

• El comportamiento asintótico de f(n)=4+6n es f(n)=n.

Comportamiento asintótico

Función• f(n)=5n + 12• f(n)=109• f(n)=n2+3n + 112• f(n)= n3+1999n + 1337• f(n)=n + sqr(n)

Comportamiento asintótico• f(n)=n• f(n)=1• f(n)=n2

• f(n)=n3

• f(n)=n

ANALICEMOS LA COMPLEJIDAD Y COMPORTAMIENTO ASINTÓTICO DEL SIGUIENTE FRAGMENTO DE CÓDIGO

Ordenamiento burbuja

for (int i = 0; i<100; i++){ num = rand() % 100; if (i>0){ for (int j = 0; j<i; j++) if (num == c[j]){ num = rand() % 100; j = -1; } } c[i] = num; } //ordenar arreglo for (int x = 0; x<100; x++){ for (int y = 0; y<99; y++){ if (c[y]>c[y + 1]){ b = c[y]; c[y] = c[y + 1]; c[y + 1] = b; } } //mostrar arreglo for (int h = 0; h<100; h++) cout << c[h] << "\t";

ANALICEMOS LA COMPLEJIDAD Y COMPORTAMIENTO ASINTÓTICO DEL ORDENAMIENTO INSERCIÓN

//ordenar arreglo for (int l = 0; l<99; l++){ pos_m = inicial(k, l); if (k[l]>k[pos_m]){ m = k[pos_m]; for (int g = pos_m - 1; g >= 1; g--){ k[g + 1] = k[g]; } k[l] = m; } for (int h = 0; h<100; h++) cout << k[h] << "\t"; cout << endl; }. . .

//parte del ordenamiento de insercionint inicial(int o[], int c){ int p = c; int d = o[c]; for (int h = c; h<100; h++){ if (o[h]<d){ d = o[h]; p = h; } } return p; }