09. Introducció a la complexitat
Introducció
En aquest mòdul s'introdueix el concepte de complexitat i d'anàlisi d'algorismes.
Quan es planteja la necessitat de resoldre un problema mitjançant el desenvolupament d'un algorisme, en la gran majoria dels casos existeixen diverses solucions possibles. En conseqüència, és necessari disposar de criteris per escollir d'entre les alternatives disponibles. Aquest mòdul analitza alguns dels criteris més utilitzats en aquest context.
Eficiència dels algorismes
De l'eficiència d'un algorisme no es deriva que aquest sigui fàcil d'escriure, modificar o entendre. En un algorisme que s'executa amb poca freqüència, el cost relatiu de desenvolupament té major pes, mentre que en un algorisme que s'executa amb molta freqüència el cost de relatiu de desenvolupament té menys importància.
L'eficiència d'un algorisme es pot quantificar segons la quantitat de recursos computacionals que s'utilitzi per a la seva execució. A major temps d'execució es pot dir que utilitzarà més recursos, per tant el temps d'execució podria ser una mesura d'eficiència. Si el que mirem és la quantitat de memòria utilitzada per l'algorisme, es podria dir que és més eficient el que consumeix menys memòria.
Una estratègia per decidir quin algorisme és el més eficient per resoldre un determinat problema d'entre un conjunt possible seria implementar tots aquests algorismes i executar-los.
Aquesta estratègia té diversos inconvenients:
- No és possible de vegades implementar tots els algorismes possibles ja que representa un esforç considerable.
- El comportament d'un algorisme en una màquina concreta no aporta suficient informació sobre com es comportarà el mateix algorisme en una altra màquina diferent.
Per tant, l'objectiu consisteix a estudiar les propietats de l'algorisme i implementar únicament la versió que es considera millor.
El temps d'execució d'un algorisme depèn habitualment de:
- Les dades d'entrada.
- La qualitat del codi generada pel compilador.
- La màquina on s'executa el programa.
- La complexitat de temps de l'algorisme basi del programa.
La complexitat d'un algorisme es defineix en funció de les dades d'entrada. Per exemple, suposem un algorisme que realitza una cerca d'un element donat en una seqüència de nombres. Si tenim la seqüència d'entrada {8, 3, 5, 7} diem que la mida de l'entrada és n = 4, sent n el nombre d'elements de la seqüència.
D'ara endavant denotarem com a T( n ) la funció de temps d'execució d'un algorisme l'entrada del qual té mida n. T( n ) s'expressa sense unitats i representa la quantitat d'operacions elementals que realitza l'algorisme, necessàries per obtenir la solució. Es consideren operacions elementals les assignacions, comparacions, operacions aritmètiques...
Exemple: temps d'execució d'una funció iterativa
La següent funció iterativa calcula la suma dels elements d'un vector:
[Exemple 09_01]
function sumVectorIterative(v: vector [N] of integer, n: integer): integer
var
i, result: integer;
end var
i := 1;
result := 0;
while i ≤ n do
result := result + v[i];
i := i + 1;
end while
return result;
end function
int sumVectorIterative(int v[N], int n) {
int i, result;
i = 0;
result = 0;
while (i < n) {
result = result + v[i];
i = i + 1;
}
return result;
}
En aquest algorisme es realitzen primer dues inicialitzacions i després un recorregut per tot el vector de n iteracions; en cada iteració es realitza una comparació (la de la condició de finalització del bucle), dues assignacions, dues operacions de suma i un accés a una posició del vector. També hi ha una evaluació extra de la condició de finalització del bucle quan aquest evalua a Fals. Donat que les comparacions, sumes, assignacions i accessos al vector es consideren operacions elementals, tenim que l'algorisme realitza 6n operacions elementals (operacions del bucle) i unes altres 3 operacions (2 al inici i 1 extra per a sortir del bucle). Per tant la funció de temps d'execució de l'algorisme és: T( n ) = 3 + 6n.
Hi ha casos en els quals l'anàlisi de la funció del temps no és tan simple i el nombre d'iteracions de l'algorisme depèn de la mida de l'entrada concreta.
Exemple: temps d'execució d'un algorisme
El següent exemple estudia el temps d'execució d'un algorisme que cerca un element en un vector:
[Exemple 09_02]
function findElemVector(v: vector [N] of integer, n: integer; key: integer): boolean
var
i: integer;
found: boolean;
end var
i := 1;
found := false;
while found = false and i ≤ n do
if v[i] = key then
found := true;
end if
i := i + 1;
end while
return found;
end function
boolean findElemVector(int v[N], int n, int key) {
int i;
boolean found;
i = 0;
found = FALSE;
while (found == FALSE && i <= n) {
if (v[i] == key) {
found = TRUE;
}
i=i+1;
}
return found;
}
En aquest algorisme es fa primer una assignació i després un bucle. Per cada iteració de bucle es realitzen tres comparacions, una operació and, una suma, un accés a vector i una assignació, totes elles operacions elementals. L'assignació dins de la sentència condicional es realitza només una vegada. La condició del bucle s'avalua una vegada més que el total d'iteracions (desprès de la darrera iteració, quan la condició del bucle avalua a fals).
Donat que el vector no està ordenat s'han de comprovar tots els elements del vector per veure si l'element es troba o no. En cas que l'element buscat no estigui en el vector, el bucle realitzarà n iteracions. En el cas que l'element estigui en la posició i = k llavors el bucle realitzarà k iteracions.
En aquest exemple té sentit parlar de temps d'execució mitjà i faria referència a la mitjana de tots els temps d'ejecucion possibles de l'algorisme. Per calcular aquest temps d'execució mitjà no obstant això, seria necessari tenir informació sobre l'entrada mitjana o la probabilitat que cada possible entrada sigui utilitzada. Aquesta informació no sempre està disponible, i d'altra banda si la coneguéssim el càlcul pot arribar a ser matemàticament molt complex. En conseqüència, quan es parli de temps d'execució T( n ) sempre es farà referència al temps d'execució del pitjor cas.
En aquest exemple el pitjor cas és quan l'element no està en el vector. Per tant, el nombre d'iteracions serà n, igual a la mida del vector.
Tenint en compte totes aquestes consideracions podem dir que el temps d'execució del pitjor cas és T( n ) = 5 + 7n.
De forma anàloga es pot parlar del millor cas, que seria quan l'element a buscar està en la primera posició del vector (k = 1). En aquest cas el temps d'execució seria constant. Aquesta mesura no proporciona una idea realista del creixement del temps d'execució de l'algorisme en augmentar la mida de l'entrada, per tant no la utilitzarem.
Aquestes mesures de temps d'execució serveixen per realitzar comparacions entre diferents implementacions d'un algorisme però no serveixen per mesurar el temps d'execució real donat que aquest depèn com s'ha comentat abans d'altres factors. Per tant, l'objectiu és comparar temps d'execució i com varia en augmentar la mida de l'entrada. Per exemple, un algorisme A amb temps d'execució T( n ) = 2n si ho comparem amb un altre temps d'execució amb T( n ) = 2n2 direm que el primer és més eficient que el segon ja que si augmenta l'entrada, el valor de T augmentarà més lentament amb el primer que amb el segon.
En resum no es pot dir que un algorisme és el més eficient de tots, sinó que solament es pot parlar que un algorisme és més eficient que un altre.
A la taula 1 es mostra una llista de funcions de temps d'execució ordenades segons la seva velocitat de creixement en augmentar la mida de l'entrada. Es comença per les quals mostren un creixement menor (més eficient) fins a l'última que té un creixement més ràpid (menys eficient). Un algorisme amb funció de temps constant T( n ) = k es considera molt eficient, ja que no importa la mida de l'entrada, l'algorisme no creix el seu temps d'execució.
Taula 1. Funcions habituals per a l'estudi de l'eficiència d'algorismes
| Velocitat de creixement | Nom |
|---|---|
| k | constant |
| log ( n ) | logarítmic |
| n | lineal |
| n . log ( n ) | quasi-lineal |
| n2 | quadràtica |
| nk | polinòmica |
| 2n | exponencial |
Notació asimptòtica
Quan diem que la funció de temps d'execució d'un algorisme T( n ) és igual a una funció f( n ), sent aquesta per exemple f( n ) = n2 o f( n ) = log ( n ), estem dient que T( n ) és proporcional a la funció f( n ).
El comportament asimptòtic d'un problema es refereix al comportament d'un algorisme quan la mida de l'entrada creix.
A un conjunt de funcions que comparteixen el mateix comportament asimptòtic li denominem ordre de complexitat. Habitualment aquests conjunts es denominen O. Cadascun d'aquests conjunts se sol identificar mitjançant un membre f( n ) que s'utilitza com a representant del conjunt o classe. Pel que direm que el conjunt de funcions "g" són de l'ordre de f( n ), és a dir que g Є O(f( n )).
En moltes situacions no és necessari conèixer el comportament exacte de l'algorisme, sinó que és suficient amb conèixer una cota superior, és a dir una funció que es comporti encara "pitjor". Així doncs direm que O(f( n )) representa al conjunt de totes les funcions g( n ) que creixen, com a molt tan ràpidament com a f( n ), on n és un nombre natural. A aquest conjunt de funcions les hi pot definir com es mostra en l'equació 1:
O(f( n )) := {g( n ) | ∃ c, n0 > 0, ∀n ≥ n0 : g( n ) ≤ c.f( n ) } (1)
L'equació 1 diu que una funció g( n ) està en el conjunt O( f ) si és possible trobar un valor n0 a partir del qual f( n ) sigui sempre major o igual que g( n ).
En definitiva el que ens indica aquesta notació és que si tenim un algorisme, el temps del qual d'execució és f( n ), podem trobar una altra funció de n, g( n ) i una mida de problema n0 de tal forma que f( n ) té sempre un temps d'execució superior per a tots els problemes de mida superior a n0.
Direm que f( x ) domina asimptòticament a g( x ), si f( x ) domina a g( x ) per a valors molt grans de x.
Per exemple, si g( n ) = n2 + 5n + 100 i f( n ) = n2 llavors f( n ) domina a g( n ) si existeix una constant de proporcionalitat c (per exemple c = 2) que permet que a partir de cert n (n=13 en aquest cas), f( n ) és sempre major que g( n ).
Aquesta notació facilitarà les comparacions d'eficiència entre algorismes diferents. A la figura 1 es mostren alguns exemples de velocitat de creixement de les funcions més comunes en l'anàlisi d'algorismes en variar n (mida de l'entrada):
Figura 1. Exemple de la velocitat de creixement de les funcions més comunes en l'anàlisi d'algorismes
Exemple: ordre de complexitat d'un algorisme
[Exemple 09_03]
for i := 1 to n
for j := 1 to n
result := i+j;
end for
end for
La sentència de la linia 3 té ordre constant, és a dir O( 1 ). Donat que la complexitat del bucle és el producte del nombre d'execucions per la complexitat de les sentències executades, el codi que va des de la linia 2 fins a la linia 4 té complexitat O( n ). El codi que va des de la linia 1 fins a la linia 5 executa el codi de la linia 3, n.n vegades, per tant l'ordre de complexitat d'aquest codi és O(n2).
Resum
En aquest mòdul hem introduït el concepte de complexitat.
Per resoldre un problema poden existir diversos algorismes. Per tant és necessari definir un criteri per decidir quin és el més adequat.
S'introdueix el concepte d'eficiència d'un algorisme relacionat amb el temps d'execució del mateix. El temps d'execució depèn de la grandària de l'entrada.
Es defineixen així el millor cas, el pitjor cas i el cas mitjà a l'hora d'analitzar els temps d'un algorisme.
Per mesurar l'eficiència s'introdueix la notació asimptòtica que ens facilitarà la comparació entre algorismes diferents.