Algorismes i com analitzar-ne la complexitat

Els algoritmes participen en gairebé totes les tasques que realitzem diàriament. Els executem molts d’ells de forma “automàtica”, sense ni tan sols adonar-nos de “per a què” s’utilitzen o “com” els fem servir. En el desenvolupament de programari, no és tan diferent. Però, què són els algoritmes de totes maneres? I per què és important analitzar la seva complexitat?

Anem a esbrinar! :)

Què és un algorisme?

Conjunt de passos necessaris per realitzar una tasca.

Els programes informàtics no són els únics que executen algoritmes, sinó que també som executats i implementats per nosaltres.

Per exemple, heu pensat en l'algorisme que executa les tasques següents?

  • Renta't les dents
  • Prendre un bany
  • Cuiner
  • Conduir a la feina des de casa

En el nostre dia a dia, executem una sèrie de passos per completar almenys una de les tasques esmentades anteriorment. Utilitzem la tasca de conducció per treballar des de casa com a exemple. Els passos que faig són bàsicament els següents:

  1. Pujar al meu cotxe
  2. Conduir a casa d’un amic per donar-los un tomb
  3. Conduir a l’oficina on treballo
  4. Aparqueu el meu cotxe al garatge del pàrquing

Aquest és el conjunt de passos (algorisme) que he de realitzar per completar aquesta tasca.

Ara, pensa en el conjunt de passos necessaris per dur a terme la mateixa tasca. És probable que siguin una mica diferents de les meves. Els nostres algoritmes poden ser diferents, però el nostre objectiu és el mateix.

Els programes informàtics no són massa diferents: hi ha diversos algoritmes que es poden utilitzar per dur a terme una sèrie de tasques. Sovint, no ens preocupem del que són, simplement les utilitzem (jo inclòs).

Per exemple, com ha de ser l’algoritme utilitzat per Waze i Google Maps, el que calcula la millor ruta entre dues ubicacions? Què passa amb l'algorisme de Netflix que suggereix pel·lícules i sèries en funció del que heu vist?

Personalment, no us ho podria dir. Tot i això, sé que són eficients. I l'eficiència és l'estàndard que fem servir per analitzar la complexitat d'un algorisme.

Què és Algorithm Complexity?

En informàtica, la complexitat d’algoritmes fa referència a quant temps i espai consumeix un algorisme per executar una tasca, segons la mida de la seva entrada.

Generalment, els algoritmes s'avaluen tant pel seu consum com en el temps i l'espai, però només vaig a abordar la complexitat horària en aquesta publicació.

L’anàlisi de la complexitat del temps ens permet determinar com es comportarà un algorisme donat un augment dels seus elements d’entrada. Podem tenir una idea del temps que trigaria a processar 10, 100 o 1000 elements.

I per què és important aquesta anàlisi?

  • Determinar quin algorisme és el més eficient;
  • Per poder desenvolupar algoritmes més eficients;
  • Per poder analitzar si la biblioteca d’un algorisme, o fins i tot el seu llenguatge real, són eficients.

En resum, l'eficiència és el punt!

Complexitat horària

El temps que es necessita per acabar una activitat.

Podem començar a analitzar el temps amb el mètode Counter de freqüència, que bàsicament compta el nombre de vegades que s’executa una instrucció de màquina. A cada pas (instrucció) se li assigna una unitat de temps, començant per 1.

El temps que consumeix l'algorisme s'expressa per la funció f (n), on n representa la mida de les dades.

El resultat d’una anàlisi s’expressa de la manera següent:

([funció que expressa temps]) = [Suma de les unitats de temps]

Ara analitzem alguns algoritmes per entendre com funciona això en realitat.

La primera funció suma dos nombres sencers:

Veiem que, per a aquesta tasca, l’algoritme implementat només executa un sol pas: la suma de dos números. Com que atribuïm un valor per a cada pas, el resultat és f (n) = 1.

Mirem el següent exemple, que és un algorisme que divideix un nombre enter per un altre nombre enter:

Tot i ser una operació matemàtica similar a la suma, l'algorisme conté més passos perquè necessita comprovar si el divisor és 0; si aquest és el cas, la divisió no es realitzarà. Com que tenim quatre passos en total, i a cadascun d'aquests se li assigna un valor d'1, el resultat és f (n) = 4.

El següent algorisme resumeix tots els elements d’una llista d’enters:

En aquest algorisme, un dels passos inclou, una instrucció de repetició; això vol dir que el codi que hi ha dins de es executarà diverses vegades. Com que el nombre d’execucions depèn de la mida de les dades, atribuïm el valor de n com a unitat de temps. El resultat és f (n) = 2n + 3.

Al següent algorisme s’afegeix la suma d’una llista amb la suma d’una segona llista.

Com a resultat, tenim f (n) = 2n² + 2n + 3.

Fins aquest moment només hem vist algoritmes simples, oi? Ara imagineu analitzar algoritmes més complexos i necessiteu fer aquests càlculs? No és gaire factible, no? Tot i que sembli el més adequat, és molt laboriós i, al final, no val la pena.

Normalment, quan analitzem un algorisme, intentem esbrinar els seus comportaments quan hi ha molts elements a processar. És en aquestes situacions que cal trobar el terme predominant de la suma de les unitats de temps.

Per exemple, quin és el terme predominant de la suma del tercer algorisme?

f (n) = 2n + 3

En aquest cas, el terme predominant en 2 * n, i explicaré per què!

En qualsevol situació en la qual n sigui superior a 1 (n> 1), el producte (el resultat de la multiplicació) ja valdrà més que el segon terme de la suma.

Prova alguna cosa: substituïu n amb qualsevol nombre enter superior a 1 i realitzeu la multiplicació.

Què passa amb el terme predominant de la suma de l’últim algoritme?

f (n) = 2n² + 2n + 3

En aquest cas, el terme predominant és 2 * n², perquè quan n> 1, el producte sempre serà superior al segon i tercer termes de la suma. Endavant, prova-ho!

Per exemple, hi ha una manera més habitual d’analitzar la complexitat dels algoritmes, on es desconeixen les constants i els termes menys significatius. Aquest mètode s’anomena Complexitat Asimptòtica.

És aquí on entra en joc l’Ordre de Complexitat, també coneguda com a Notació-O o Big-O.

Nota gran

S'utilitza per classificar un algorisme tenint en compte la taxa de creixement de les operacions a mesura que creix el nombre d'elements processats.

La notació Big-O també defineix una funció que expressa la complexitat horària d’un algorisme. A aquest efecte, n s'utilitza n com a funció de la lletra O.

Les classes més comunes són:

  • O (1): constant, el nombre d'operacions no augmenta a mesura que augmenta el nombre d'elements
  • O (log n): logarítmic, el nombre d’operacions és inferior al nombre d’elements
  • O (n): Lineal, el nombre d’operacions augmenta proporcionalment amb el nombre d’elements
  • O (n²) Quadràtic, el nombre d’operacions serà superior al nombre d’elements
  • O (2 ^ n) - Exponencial, el nombre d'operacions augmenta ràpidament en comparació amb el nombre d'elements
  • O (n!) - Factorial, el nombre d’operacions augmenta molt, molt ràpidament, fins i tot per a un nombre reduït d’elements

A continuació, tenim un gràfic que mostra la taxa de creixement d’operacions x la quantitat d’elements:

El gràfic es classifica de la següent manera:

  • La zona vermella és terrible, evita-ho!
  • La zona taronja és dolenta, també evita-la!
  • La zona groga és justa, raonable.
  • La zona de color verd clar és bona, genial.
  • La zona de color verd fosc és excel·lent, felicitats!

Ara, utilitzarem la notació Big-O per categoritzar els algoritmes esmentats anteriorment, sempre utilitzant el terme predominant per guiar-nos.

El primer algorisme va resultar en f (n) = 1; és a dir, que independentment d’un augment d’elements, l’algoritme només executa una operació. Així, podem classificar l'algorisme com a Constant - O (1).

El segon algorisme va resultar en f (n) = 4; és a dir, que independentment d’un augment d’elements, l’algoritme executarà quatre operacions. Així, també podem classificar aquest algorisme com a Constant - O (1).

El resultat del tercer algorisme va ser f (n) = 2n + 3; és a dir, que el nombre d’operacions creixerà proporcionalment amb el nombre d’elements, veient com n serveix de variable en aquesta funció. Així, podem definir aquest algorisme com Lineal - O (n).

El resultat de l'últim algorisme va donar lloc a f (n) = 2n² + 2n + 3, el que significa que el nombre d'operacions augmentarà més que el nombre d'elements. En aquest cas, n també serveix de variable, però s’eleva a la segona potència (quadrada). Així, podem definir aquest algorisme com Quadràtic - O (n²).

La taula següent mostra el creixement del nombre d’operacions en relació amb el creixement del nombre d’elements.

Tingueu en compte que en un algorisme exponencial, 16 elements tindrien com a resultat almenys 65.5536 operacions. Bastant inquietant, oi?

En general, el procés d’anàlisi és el mateix que hem estat fent: comptar el nombre de passos i identificar el terme predominant.

Algunes tendències que podem observar:

  • Els algorismes que no tenen un bucle de repetició solen ser constants - O (1)
  • Els algoritmes que tenen bucles de repetició, sempre que no estiguin imbricats, solen ser lineals: O (n)
  • Els algoritmes que tenen dos bucles de repetició nidificats solen ser quadràtics: O (n²)
  • L’accés directe a l’índex d’una matriu sol ser O (1) (constant)
  • Els mètodes d'extensió de llista, de mitjana, són O (n). Per exemple: qualsevol, suma i filtre.
  • Algorismes d’ordenació com Ordre de bombolla, Sort d’inserció i Ordre de selecció solen ser O (n²).

Saber classificar algorismes ens proporciona la capacitat de jutjar l’eficàcia o la ineficàcia d’un algorisme. Per descomptat, no podem mesurar el seu temps de funcionament exacte en segons, minuts o hores. Per fer-ho, cal executar-lo, mesurar-lo i alterar-lo en conseqüència. T’imagines fer això per algoritmes que tinguin hores, o fins i tot dies, a córrer? De cap manera!

Espero haver complert l'objectiu d'aquest post, que era donar una visió general dels algoritmes i la seva anàlisi mitjançant el mètode de recompte de freqüència i Big-O.

A continuació, us he deixat algunes referències com a material addicional de lectura.

Referències:

Vídeos 1 a 1.7

Voleu aportar la innovació al mercat de préstecs a través de la tecnologia? Sempre estem buscant gent nova per unir-se a la nostra tripulació.

Consulteu les nostres obertures aquí.