SEDE MANIZALES DNSAV

REGLAS BASICAS PARA EL CALCULO DE LA COMPLEJIDAD

Aunque no es posible encontrar una fórmula que siempre funcione para calcular la complejidad de un algoritmo, si es posible encontrar una serie de pautas que nos permitirán de una manera lógica llegar a su cálculo. Los algoritmos bien estructurados están conformados por una combinación de las siguientes instrucciones: a. Sentencias simples Se denominan sentencias simples, aquellas que tienen que ver con la asignación, operaciones matemáticas básicas, entrada / salida, etc. siempre y cuando no trabajen sobre variables estructuradas cuyo tamaño este relacionado con el tamaño del problema (lectura o escritura de arreglos, archivos, puertos). La inmensa mayoría de las sentencias simples de un algoritmo requieren un tiempo constante de ejecución, siendo su complejidad O(1). Ejemplos: x=1 y=z+x+w; scanf(“%d”,&x); printf(“%d”,x); cada una de las anteriores instrucciones de forma independiente tienen complejidad de O(1). b. Condicionales (if - else) Los condicionales suele ser O(1), a menos que estos involucren un llamado a un procedimiento, y siempre se le debe sumar la peor complejidad posible de las alternativas del condicional, bien en la rama afirmativa, o bien en la rama negativa. En decisiones múltiples (switch) se tomará la peor de todas las ramas. Ejemplos:
	If (a>b)
		{
			for (x=1; x<=n; x++)
				suma += x;
	} else {
				suma=0;
	}
La parte cierta del condicional es un ciclo que se repite n veces, por lo tanto su complejidad es O(n), mientras que la parte negativa es una asignación simple con complejidad O(1); por lo tanto la complejidad del condicional está dada por la mayor complejidad entre la parte afirmativa y la negativa del mismo, siendo entonces O(n) la complejidad total del condicional. c. Ciclos (while, for, do-while) En los ciclos con un contador explícito, se distinguen dos casos: que el tamaño n forme parte de los límites del ciclo, con una complejidad basada en n y dependiente de la forma como avanza el ciclo hacia su terminación; si el ciclo se realiza un número constante de veces, independiente de n, entonces la repetición sólo introduce una constante multiplicativa que puede absorberse, dando como resultado O(1). Ejemplos: Si el ciclo es de tamaño constante(k es un valor constante)

	For (i=0; i<k; i++) {
		Sentencias simples
	}

La complejidad es: k*O(1) ---> O(1)
Si el tamaño n aparece como el límite de las iteraciones:
	For (i=0; i<n; i++) {
			Sentencias simples
	}
La complejidad es: n * O(1) ----> O(n)
O si los ciclos son anidados:
	For (i=0; i<n; i++) {
		For (j=0; j<n; j++)
			{
				Sentencias simples
			}
	}
La complejidad es: n n O(1) ----> O(n²) Para ciclos anidados pero con variables dependientes:

	For (i=0; i<n; i++) {
			For (j=0; j<i; j++) {
				Sentencias simples
			}
	}

Teniendo en cuenta que el bucle exterior se realiza n veces, mientras que el interior se realiza primero una, luego dos, después tres y así hasta n.: 1 + 2 + 3 + ... + n = n*(n+1)/2 ----> la complejidad es : O(n²) A veces aparecen ciclos multiplicativos, donde la evolución de la variable de control no es lineal (como en los casos anteriores)

	c= 1;while (c <n) {
		c= 2 c;*
	}

El valor inicial de la variable c es 1, llegando a 2ⁿ al cabo de n - iteraciones. El número de iteraciones es tal que 2^k >= n >= k (log₂ (n)) y, por tanto, la complejidad del ciclo es O(log² n). El siguiente es un ejemplo en el cual la variable se divide cada vez a la mitad:
	c= n;while (c > 1) {
		c= c / 2;
	}
Un razonamiento análogo nos lleva a log2n iteraciones y, por tanto, a un orden O(log² n) de complejidad. y la combinación de los anteriores:

	for (i=0; i<n; i++) {
		c=i; while (c>0) {
			c=c/2;
		}
	}
se tiene un bucle interno de orden O(log² n) que se ejecuta n veces en el ciclo externo; luego el ejemplo es de orden O(n log²n) d. Llamadas a procedimientos La complejidad de llamar a un procedimiento viene dada por la complejidad del contenido del procedimiento en sí. El costo del llamado es una constante que podemos obviar inmediatamente dentro de nuestro análisis. El cálculo de la complejidad asociada a un procedimiento puede complicarse si se trata de procedimientos recursivos, los cuales requieren de un proceso más detallado y complejo. Ejemplos: Si hay varias instrucciones y entre ellas un llamado a una función.

	for (i=0; i<n; i++) {
		insertar(arreglo, i);
	}

Hay un ciclo que se realiza n veces, lo que generaría un complejidad de O(n), pero como en su interior hay un llamado a la función insertar, la complejidad del ciclo estará multiplicada por la complejidad de la función insertar. Si hay dos o más llamados a funciones. ordenar(arreglo, n); mostrar(arreglo, n) Suponiendo que ordenar organiza un vector mediante el método rápido (Quick-Sort) con una complejidad de O(n log² n), y que mostrar simplemente presenta el contenido del arreglo en la pantalla con una complejidadde O(n). La complejidad total será la mayor de los dos llamados a las funciones,resultando O(n log² n).
e. Secuencias de instrucciones La complejidad de una serie de instrucciones de un programa es del orden de la suma de las complejidades individuales, aplicándose las operaciones antes expuestas. Ejemplos: Veamos el análisis de un simple enunciado de asignación a una variable entera: a = b; Como el enunciado de asignación toma tiempo constante, está enO(1). Consideremos un simple ciclo for:

	sum=0; for(i=1; i<=n; i++)
		sum += n;
Laprimera línea es de complejidad constante O(1). El ciclo for es repetido n veces. La tercera línea toma también un tiempo constante, por la regla de simplificación (4), el costo total por ejecutar las dos líneas que forman el ciclo for es O(n). Por la regla (3), el costodelfragmento de código es tambiénO(n). Analicemos un fragmento de código con varios ciclos for, dos de los cuales están anidados.

	sum=0; for(j=1; j<=n; j++)
		for(i=1; i<=j; i++)
			sum++;
	for(k=1; k<=n; k++)
		A[k]= k-1;

Este código tiene tres partes: una asignación, y dos ciclos. La asignación toma tiempo constante, llamémosla c₁. El segundo ciclo es similar al ejemplo anterior y toma c₂n= O(n). Analicemos ahora el primer ciclo, que es un doble ciclo anidado. En este caso trabajemos de adentro hacia fuera. La expresión sum++ requiere tiempo constante, se le llamará c₃. Como el ciclo interno es ejecutado j veces, por la regla (4), tiene un costo de c₃* j. El ciclo exterior es ejecutado n veces, pero cada vez el costo del ciclo interior es diferente. El costo total del ciclo es: c₃ veces la suma de los números del 1 al n, es decir La suma de 1,2,,,, n == n(n+1)/2, que es una complejidad de O(n²). Por la regla (3),O(c1+c2n+c3n²) es simplemente O(n²). Comparemos el análisis de los siguientes fragmentos de código:

	sum1=0; for(i=1; i<=n; i++)
		for(j=1; j<=n; j++)
			sum1++;

	sum2=0; for(i=1; i<=n; i++)
		for(j=1; j<=i; j++)
			sum2++;

El primer fragmento ejecuta la instrucción sum1++n² veces, por otra parte, el segundo fragmento de código tiene un costo aproximado de ½ n². Así ambos códigos tienen un costo de O(n²). Es bueno analizar el siguiente ejemplo en el cual se aprecia que no siempre los ciclos anidados tienen complejidad O(n²):

	sum1=0; for(k=1; k<=n; k=2)*
		for(j=1; j<=n; j++)
			sum1++;
Como el primer ciclo se realiza log₂ n veces y el interno n veces, entonces el algoritmo tiene un costo de O(n log n).

b. Condicionales (if - else)

c. Ciclos (while, for, do-while)

d. Llamadas a procedimientos

e. Secuencias de instrucciones