Ce este un algoritm eficient? Cum construim un algoritm eficient?

  


Pentru a înțelege mai bine ce înseamnă un algoritm eficient vom începe cu un exemplu:


Enunț: Să se verifice dacă un număr N este prim.


Definiția numărului prim o găsiți aici: https://ro.wikipedia.org/wiki/Num%C4%83r_prim 

Pe scurt: Un număr prim este un număr care se împarte doar la 1 și la el însuși. Atenție: 1 nu este număr prim.


Prima metodă prezentată este următoarea: 


Această metodă presupune parcurgerea tuturor numerelor de la 2 la N-1.


Însă putem observa că nu toate numerele din [2, N-1] pot fi divizorii lui N. Spre exemplu niciodată N nu poate avea divizori mai mari decât N/2. Mai mult decât atât, matematica ne-a mai învățat faptul că divizorii sunt mereu în perechi și atunci dacă nu găsim un divizor din intervalul [2,√N], sigur nu există nici în  [√N, N).


Atunci a doua metodă este următoarea:



Presupunând că pentru fiecare operație de tipul N%div calculatorului i-ar lua o milisecundă (ms), iar numărul N ar fi prim (acesta fiind cel mai rău caz pentru că implică parcurgerea tuturor numerelor din intervalul  [2, N-1], respectiv [2,√N]) vom obține următoarele rezultate:


Pentru N = 7 / N = 251 / N = 10,000,000,019 (1010 + 19)


Metoda 1: 5ms /249ms /10,000,000,017ms (~ 115 zile)

Metoda 2: 1ms /14ms /105 ms (~2 min)


Analizând din acest punct de vedere putem observa că a doua metodă este mult mai eficientă decât prima.


Eficiența poate fi de două tipuri:

  • eficiența de memorie
  • eficiența de timp


La BAC Subiectul III, exercițiul 3 implică proiectarea unui algoritm eficient din punctul de vedere al spațiului de memorie și al timpului de execuție.


Ponturi pentru a crea un algoritm eficient la bac:

  • încearcă pe cât posibil să nu folosești tablouri unidimensionale sau bidimensionale (vectori și matrici)
  • utilizează variabile simple și cât se poate de puține
  • testează-l pe cazurile cele mai rele
  • scrie un cod cât mai concis și clar, în mod normal nu ar trebui să îți ia mai mult de o pagină să scrii codul






Ți-a plăcut articolul? Dă-i share 😄

Articolul anterior Un secret
Articolul urmator Teze, Vacante, BAC, EN 2022
Back
x
Acest website utilizează cookie-uri pentru a creea o experiență cât mai plăcută. Învață mai multe Acceptă