Eficiencia

Metodologies de la Programació

Càlcul de l'eficiència
Què veurem en aquest bloc?
Una introducció al càlcul del cost temporal
d'un programa a partir del seu codi.
Formes de creixement, Ordres de complexitat

Metodologies de la Programació

Introducció
• Un algorisme és més eficient que un
altre si realitza les mateixes tasques
amb menys recursos.
• Els recursos considerats solen ser:
– Tempsd’execució (càrrega de la CPU)
– Espai de memòria (variables)
• En aquest tema ens centrarem en
l’eficiència temporal. Per l’eficiència
espaial cal comparar el tamany de les
variables usades pels 2 algorismes.

Metodologies de la Programació

Exemple de cost temporal
• Suposem que volem ordenar de manera
creixent un volum d'elements gran (més
d'un milió) que hi ha emmagatzemats en un
vector, i tenimdisponible un PC. Hi ha dos
algorismes clàssics que resolen aquest
problema: quicksort i bombolla. El temps
d’execució de cadascun en un PC concret
ha estat de:
– Algorisme Quicksort: 17 segons
– Algorisme Bombolla: 1700 minuts
= 2 dies, 5 hores i 40 minuts

Metodologies de la Programació

Factors que determinen l’eficiència
• Grandària de les dades d'entrada: quantes
dades hem de tractar perresoldre un cas
concret. Normalment serà variable, i ho
denotarem com N.
• Contingut de les dades d'entrada: quines
dades concretes. Normalment no ho sabrem
i considerarem el cas pitjor.
• Codi generat: aquest factor fa referència al
llenguatge utilitzat. Quan ignorem aquest
factor s’anomena Criteri Asimptòtic.

Metodologies de la Programació

Ordres de complexitat
Essent n el tamany de les dades atractar
per l’algorisme:
• Cota superior (cas pitjor): O (n)
• Cota inferior (cas millor): Ω (n)
Nosaltres treballarem amb la cota superior

Metodologies de la Programació

Formes de creixement (1)
Constant

O(1)

Logarítmic

O(log2n)

Lineal

O(n)

Quasilineal

O(n log2n)

Quadràtic

O(n2)

Cúbic

O(n3)

Polinòmic

O(nk) amb k conegut

Exponencial

O(kn) amb k conegut

Factorial

O(n!)

Formesde creixement (2)
Metodologies de la Programació

Cúbic O(n3)

Quadràtic
O(n2)

Quasi-lineal
O(n·log n)

Lineal O(n)

Quantitat de dades petita, per sota de 100 valors

3

Metodologies de la Programació

Cúbic O(n )

Quadràtic
O(n2)

Formes de creixement (3)
Quasi-lineal
O(n·log n)

Lineal O(n)

Quantitat de dades gran

Metodologies de la Programació

Formes de creixement (4)

Relació entre eltamany del conjunt de dades (n)
i el temps que es necessita per tractar-les
segons la complexitat de l'algorisme

Metodologies de la Programació

Formes de creixement (5)

temps

log n

n

n log n

n2

n3

10

1E+10

10

10

3

2

20

1E+20

20

16

4

2

30

1E+30

30

22

5

3

40

1E+40

40

27

6

3

50

1E+50

50

32

7

3

Vegem-ho al revés:
Quantes dades puc tractar donat un interval detemps determinat segons cada forma de
creixement ?

Metodologies de la Programació

Problemes inabordables

Exponencial
Factorial

Metodologies de la Programació

Càlcul de la complexitat d’un
algorisme
• Donat un algoritme, definirem un mètode
per calcular quin és el seu grau de
complexitat
• Recordeu que estudiarem el cas pitjor
• I que mantindrem el criteri asimptòtic, és
a dir, tant ens fa enquin llenguatge
s'implementi l'algoritme posteriorment.

Metodologies de la Programació

Càlcul de la complexitat d’un
algorisme (1)
1. Comencem per les instruccions més
internes. Després les externes.
2. Les instruccions que no depenen de n,
tenen cost O(1)
3. Composició seqüencial: Regla de la suma
Instruccio1 O(f(n))
Instruccio2 O(g(n))
Cost total: O(f(n))+O(g(n)) = max(f(n),g(n))

Metodologiesde la Programació

Càlcul de la complexitat d’un
algorisme (2)
1. Instrucció condicional:
Si C llavors S1 sino S2 fsi
S’aplica la regla de la suma entre el cost de C, S1 i S2

2. Instrucció iterativa: Regla del producte
mentre C fer
S
fmentre;
Cost de C+S = O(f(n))
Nombre d’iteracions màxim: O(g(n))
Cost total: O(f(n)) * O(g(n)) = O(f(n)*g(n))

Exemple:

Metodologies de la Programació

El...