Kaip nustatoma algoritmo efektyvumas ir sudėtingumas?

Algoritmo efektyvumas ir sudėtingumas paprastai vertinami naudojant laiko ir erdvės sudėtingumo analizę.

• Laiko sudėtingumas rodo, kaip algoritmo vykdymo laikas priklauso nuo įvesties duomenų dydžio. Paprastai jis išreiškiamas "Big O" notacija, pavyzdžiui, O(n), O(n²), O(log n).
• Erdvės sudėtingumas atspindi, kiek atminties reikalinga algoritmui priklausomai nuo įvesties duomenų dydžio.

Sudedamumo nustatymui analizuojama pagrindinių operacijų (pavyzdžiui, palyginimų, priskyrimų) skaičius blogiausiu, vidutiniu ir geriausiu atveju.

Pavyzdys: burbuliukų rūšiavimas turi laiko sudėtingumą O(n²), nes blogiausiu atveju reikia atlikti apie n² palyginimų.

Taip pat efektyvumą galima matuoti empiriškai, paleidus algoritmą su skirtingais duomenų kiekiais ir matuojant laiką bei atminties naudojimą.