Eficàcia algorísmica

En informàtica, l'eficiència algorísmica és una propietat d'un algorisme que es relaciona amb la quantitat de recursos computacionals utilitzats per l'algorisme. S'ha d'analitzar un algorisme per determinar el seu ús de recursos, i l'eficiència d'un algorisme es pot mesurar en funció de l'ús de diferents recursos. L'eficiència algorítmica es pot considerar anàloga a la productivitat d'enginyeria per a un procés repetitiu o continu.^[1]

Per obtenir la màxima eficiència, és desitjable minimitzar l'ús de recursos. No obstant això, diferents recursos, com ara la complexitat del temps i l'espai, no es poden comparar directament, de manera que quin dels dos algorismes es considera més eficient sovint depèn de quina mesura d'eficiència es considera més important.^[2]

Per exemple, bubble sort i timsort són algorismes per ordenar una llista d'elements del més petit al més gran. L'ordenació de bombolles ordena la llista en temps proporcional al nombre d'elements al quadrat ( ${\textstyle O(n^{2})}$ , vegeu la notació O gran), però només requereix una petita quantitat de memòria addicional que és constant respecte a la longitud de la llista ( ${\textstyle O(1)}$ ). Timsort ordena la llista en temps linearitmic (proporcional a una quantitat multiplicada per el seu logaritme) a la longitud de la llista ( ${\textstyle O(n\log n)}$ ), però té un requisit d'espai lineal a la longitud de la llista ( ${\textstyle O(n)}$ ). Si les llistes grans s'han d'ordenar a gran velocitat per a una aplicació determinada, timsort és una millor opció; tanmateix, si minimitzar la petjada de memòria de l'ordenació és més important, l'ordenació de bombolles és una millor opció.^[3]

Rerefons

La importància de l'eficiència respecte al temps va ser emfatitzada per Ada Lovelace el 1843 aplicada al motor analític mecànic de Charles Babbage:

"En gairebé tots els càlculs és possible una gran varietat d'arranjaments per a la successió dels processos, i diverses consideracions han d'influir en les seleccions entre ells per als propòsits d'un motor de càlcul. Un objectiu essencial és triar aquella disposició que tendirà a reduir-se a un mínim el temps necessari per completar el càlcul"

Els primers ordinadors electrònics tenien una velocitat limitada i una memòria d'accés aleatori limitada. Per tant, es va produir una compensació espai-temps. Una tasca podria utilitzar un algorisme ràpid amb molta memòria, o podria utilitzar un algorisme lent amb poca memòria. El compromís d'enginyeria va ser llavors utilitzar l'algoritme més ràpid que pogués cabre a la memòria disponible. Els ordinadors moderns són significativament més ràpids que els ordinadors primerencs i tenen una quantitat molt més gran de memòria disponible (gigabytes en lloc de kilobytes). No obstant això, Donald Knuth va subratllar que l'eficiència encara és una consideració important:

"En les disciplines d'enginyeria establertes una millora del 12%, fàcil d'obtenir, mai es considera marginal i crec que el mateix punt de vista hauria de prevaldre en l'enginyeria del programari"

Visió general

Es considera que un algorisme és eficient si el seu consum de recursos, també conegut com a cost computacional, està a un nivell acceptable o per sota. A grans trets, "acceptable" vol dir: s'executarà en una quantitat de temps o espai raonable en un ordinador disponible, normalment en funció de la mida de l'entrada. Des de la dècada de 1950, els ordinadors han experimentat un augment espectacular tant de la potència computacional disponible com de la quantitat de memòria disponible, de manera que els nivells acceptables actuals haurien estat inacceptables fins i tot fa 10 anys. De fet, gràcies a la duplicació aproximada de la potència de l'ordinador cada 2 anys, les tasques que són acceptablement eficients en telèfons intel·ligents moderns i sistemes integrats poden haver estat inacceptablement ineficients per als servidors industrials fa 10 anys.

Els fabricants d'ordinadors presenten sovint nous models, sovint amb un rendiment superior. Els costos del programari poden ser bastant elevats, de manera que, en alguns casos, la manera més senzilla i barata d'aconseguir un rendiment més alt podria ser comprar un ordinador més ràpid, sempre que sigui compatible amb un ordinador existent.

Anàlisi teòrica

En l'anàlisi teòrica dels algorismes, la pràctica habitual és estimar la seva complexitat en el sentit asimptòtic. La notació més utilitzada per descriure el consum de recursos o "complexitat" és la notació Big O de Donald Knuth, que representa la complexitat d'un algorisme en funció de la mida de l'entrada. ${\textstyle n}$ . La notació O gran és una mesura asimptòtica de la complexitat de la funció, on ${\textstyle f(n)=O{\bigl (}g(n){\bigr )}}$ aproximadament significa que el requeriment de temps per a un algorisme és proporcional a $g(n)$ , ometent termes d'ordre inferior que contribueixen menys de $g(n)$ al creixement de la funció com ${\textstyle n}$ creix arbitràriament. Aquesta estimació pot ser enganyosa quan ${\textstyle n}$ és petit, però en general és prou precís quan ${\textstyle n}$ és gran ja que la notació és asimptòtica. Per exemple, l'ordenació per bombolles pot ser més ràpida que l'ordenació per fusió quan només s'han d'ordenar uns quants elements; no obstant això, és probable que qualsevol implementació compleixi els requisits de rendiment per a una llista petita. Normalment, els programadors estan interessats en algorismes que s'escallin de manera eficient a mides d'entrada grans, i es prefereix l'ordenació de fusió a l'ordenació de bombolles per a les llistes de longitud que es troben a la majoria de programes intensius en dades.^[4]

Alguns exemples de notació Big O aplicada a la complexitat temporal asimptòtica dels algorismes inclouen:

Notació	Nom	Exemples
$O(1)$	constant	Trobar la mediana d'una llista ordenada de mesures; Utilitzant una taula de cerca de mida constant; Ús d'una funció hash adequada per buscar un element.
$O(\log n)$	logarítmica	Trobar un element en una matriu ordenada amb una cerca binària o un arbre de cerca equilibrada, així com totes les operacions en un munt binomial.
$O(n)$	lineal	Trobar un element en una llista sense ordenar o un arbre amb format incorrecte (el pitjor dels casos) o en una matriu sense ordenar; Suma de dos nombres enters de n bits mitjançant ripple carry.
$O(n\log n)$	linearitmica, loglineal o quasilineal	Realització d'una transformada ràpida de Fourier ; heapsort, quicksort (cas millor i mitjà) o merge sort
$O(n^{2})$	quadràtica	Multiplicar dos nombres de n xifres per un algorisme simple ; classificació de bombolles (el pitjor dels casos o implementació ingènua), ordenació de Shell, classificació ràpida (pitjor cas), ordenació per selecció o ordenació per inserció
$O(c^{n}),\;c>1$	exponencial	Trobar la solució òptima (no aproximada) al problema del venedor ambulant mitjançant la programació dinàmica ; determinar si dues declaracions lògiques són equivalents mitjançant la cerca de força bruta