Įvadas į algoritmų laiko sudėtingumą

Informatikos srityje algoritmų analizė yra labai svarbi dalis. Svarbu rasti efektyviausią problemos sprendimo algoritmą. Problemai išspręsti galima turėti daug algoritmų, tačiau čia iššūkis yra pasirinkti efektyviausią.

Dabar esmė ta, kaip mes galime atpažinti efektyviausią algoritmą, jei turime įvairių algoritmų rinkinį? Čia atsiranda algoritmų erdvės ir laiko sudėtingumo samprata. Erdvės ir laiko sudėtingumas veikia kaip algoritmų matavimo skalė. Algoritmus lyginame pagal jų erdvę (atminties kiekį) ir laiko sudėtingumą (operacijų skaičių).

Bendras kompiuterio atminties kiekis, kurį naudoja algoritmas, kai jis vykdomas, yra to algoritmo erdvės sudėtingumas. Šiame straipsnyje neaptarsime kosmoso sudėtingumo (kad šis straipsnis būtų šiek tiek mažesnis).

Laiko kompleksiškumas

Taigi laiko sudėtingumas yra operacijų, kurias algoritmas atlieka atlikdamas savo užduotį, skaičius (atsižvelgiant į tai, kad kiekviena operacija užima tiek pat laiko). Algoritmas, atliekantis užduotį mažiausiai operacijų, laikomas efektyviausiu laiko sudėtingumo požiūriu. Tačiau erdvės ir laiko sudėtingumui taip pat turi įtakos tokie veiksniai kaip jūsų operacinė sistema ir aparatinė įranga, tačiau mes jų neįtraukiame į šią diskusiją.

Dabar, norėdami suprasti laiko sudėtingumą, paimsime pavyzdį, kuriame palyginsime du skirtingus algoritmus, kurie naudojami tam tikrai problemai išspręsti.

Problema yra paieška. Turime ieškoti elemento masyve (šioje problemoje manysime, kad masyvas yra rūšiuojamas didėjimo tvarka). Norėdami išspręsti šią problemą, turime du algoritmus:

1. Tiesinė paieška.

2. Dvejetainė paieška.

Tarkime, masyve yra dešimt elementų, ir mes turime surasti masyvo skaičių dešimt.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;

Linijinis paieškos algoritmas palygins kiekvieną masyvo elementą su „ search_digit“ . Kai jis randa search_digit masyve, jis grįš tiesa .

Dabar suskaičiuokime jo atliekamų operacijų skaičių. Čia atsakymas yra 10 (nes jis lygina kiekvieną masyvo elementą). Taigi, tiesinei paieškai naudojamas dešimt operacijų norint rasti duotą elementą (tai yra didžiausias šio masyvo operacijų skaičius; tiesinės paieškos atveju tai taip pat žinoma kaip blogiausias algoritmo atvejis).

Apskritai, tiesinei paieškai blogiausiu atveju prireiks n operacijų skaičiaus (kur n yra masyvo dydis).

Panagrinėkime šio atvejo dvejetainės paieškos algoritmą.

Dvejetainę paiešką galima lengvai suprasti pagal šį pavyzdį:

Šaltinis: „Learneroo“

Jei bandysime pritaikyti šią logiką savo problemai, pirmiausia palyginsime „ search_digit“ su viduriniu masyvo elementu, t. Y. 5. Kadangi 5 yra mažesnis nei 10, tada mes pradėsime ieškoti „ search_digit “ masyvo elementuose didesnis nei 5, tuo pačiu būdu, kol gausime norimą elementą 10.

Dabar pabandykite suskaičiuoti dvejetainės paieškos operacijų skaičių norimam elementui rasti. Tai užtruko maždaug keturias operacijas. Tai buvo blogiausias dvejetainės paieškos atvejis. Tai rodo, kad tarp atliktų operacijų skaičiaus ir bendro masyvo dydžio yra logaritminis ryšys.

operacijų skaičius = log (10) = 4 (apytiksliai)

2 bazei

Šį binarinės paieškos rezultatą galime apibendrinti taip:

N dydžio masyvui operacijų, kurias atlieka dvejetainė paieška, skaičius yra toks: log (n)

Didysis O žymėjimas

Ankstesniuose teiginiuose matėme, kad n masyvo dydžiui n tiesinė paieška atliks n operacijas, kad užbaigtų paiešką. Kita vertus, atliekant dvejetainę paiešką buvo atliktas log (n) operacijų skaičius (tiek blogiausiais atvejais). Tai galime pavaizduoti kaip grafiką ( x ašis : elementų skaičius, y ašis : operacijų skaičius).

Šaltinis: Techtud

Iš paveikslo yra visiškai aišku, kad linijinės paieškos sudėtingumo padidėjimo greitis yra daug greitesnis nei dvejetainės paieškos.

Analizuodami algoritmą, mes naudojame žymėjimą, kad atspindėtume jo laiko sudėtingumą, o tas žymėjimas yra „Big O“ žymėjimas.

Pavyzdžiui: Linijinės paieškos laiko sudėtingumas gali būti pateiktas kaip O (n) ir O (log n) dvejetainės paieškos atveju (kur n ir log (n) yra operacijų skaičius).

Toliau išvardyti kai kurių populiarių algoritmų sudėtingumas pagal laiką arba „Big O“:

  1. Dvejetainė paieška: O (log n)
  2. Linijinė paieška: O (n)
  3. Greitas rūšiavimas: O (n * log n)
  4. Pasirinkimo rūšiavimas: O (n * n)
  5. Keliaujantis pardavėjas: O (n!)

Išvada

Aš labai vertinu jūsų pastangas, jei vis dar skaitote šį straipsnį. Dabar jūs tikriausiai galvojate - kodėl taip svarbu suprasti laiko sudėtingumą?

Mes žinome, kad nedaugeliui elementų (sakykime 10), skirtumas tarp dvejetainės paieškos ir tiesinės paieškos atliekamų operacijų skaičiaus nėra toks didelis. Tačiau realiame pasaulyje dažniausiai mes sprendžiame problemas, turinčias didelius duomenų gabalus.

Pavyzdžiui, jei turime 4 milijardus elementų, kurių reikia ieškoti, blogiausiu atveju linijinei paieškai atlikti reikės 4 milijardų operacijų. Dvejetainė paieška atliks šią užduotį atlikdama tik 32 operacijas. Tai didelis skirtumas. Tarkime, jei viena operacija užtruks 1 ms, tada dvejetainė paieška užtruks tik 32 ms, o linijinė paieška užtruks 4 milijardus ms (tai yra maždaug 46 dienos). Tai reikšmingas skirtumas.

Tai yra priežastis, kodėl laiko sudėtingumo studijavimas tampa svarbus, kai kalbama apie tokį didelį duomenų kiekį.

Ištekliai

Grokčiojantys algoritmai - Aditya Y Bhargava

CS Dojo įvadas į Big O žymėjimą ir laiko sudėtingumą