Sissejuhatus algoritmide ajalisse keerukusse

Arvutiteaduses on algoritmide analüüs väga oluline osa. Oluline on leida probleemi lahendamiseks kõige tõhusam algoritm. Probleemi lahendamiseks võib olla palju algoritme, kuid siin on väljakutse valida kõige tõhusam.

Nüüd on küsimus selles, kuidas saaksime ära tunda kõige tõhusama algoritmi, kui meil on komplekt erinevaid algoritme? Siin tekib algoritmide ruumi ja aja keerukuse mõiste. Ruumi ja aja keerukus toimib algoritmide mõõteskaalana. Algoritme võrreldakse nende ruumi (mälu maht) ja aja keerukuse (toimingute arv) põhjal.

Algoritmi poolt selle käivitamisel kasutatud arvuti mälu kogusumma on selle algoritmi ruumiline keerukus. Me ei käsitle selles artiklis ruumi keerukust (selle artikli natuke väiksemaks muutmiseks).

Aja keerukus

Niisiis, aja keerukus on toimingute arv, mille algoritm oma ülesande täitmiseks teeb (arvestades, et iga toiming võtab sama palju aega). Algoritmi, mis täidab ülesannet kõige väiksema arvu toimingutega, peetakse ajalise keerukuse mõttes kõige tõhusamaks. Ruumi ja aja keerukust mõjutavad aga ka sellised tegurid nagu teie opsüsteem ja riistvara, kuid me ei hõlma neid sellesse arutelusse.

Aja keerukuse mõistmiseks võtame näite, milles võrdleme kahte erinevat algoritmi, mida kasutatakse konkreetse probleemi lahendamiseks.

Probleemiks on otsimine. Peame massiivi elemendi otsima (selles probleemis eeldame, et massiiv on järjestatud kasvavas järjekorras). Selle probleemi lahendamiseks on meil kaks algoritmi:

1. Lineaarne otsing.

2. Binaarotsing.

Oletame, et massiiv sisaldab kümmet elementi ja peame massiivist leidma numbri kümme.

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

Lineaarse otsingu algoritm võrdleb massiivi kõiki elemente otsingu_arvuga . Kui ta leiab massiivilt otsingu_numbri , naaseb see tõeks .

Nüüd loendame selle toimingute arvu. Siin on vastus 10 (kuna see võrdleb massiivi kõiki elemente). Niisiis kasutab lineaarotsing antud elemendi leidmiseks kümmet toimingut (see on selle massiivi maksimaalne toimingute arv; lineaarse otsingu korral on see tuntud ka kui algoritmi halvim juhtum).

Üldiselt võtab lineaarotsing halvimal juhul n arvu toiminguid (kus n on massiivi suurus).

Uurime selle juhtumi binaarotsingu algoritmi.

Binaarotsingut saab selle näite abil hõlpsasti mõista:

Allikas: Learneroo

Kui me püüame rakendada seda loogikat meie probleem siis esiteks me võrrelda search_digit Lähis massiivi element, mis on 5. Nüüd, kuna 5 on alla 10, siis me hakata otsima search_digit massiivi elemendid suurem kui 5, samal viisil, kuni saame soovitud elemendi 10.

Proovige nüüd loendada vajalike elementide leidmiseks binaarse otsingu toimingute arvu. Selleks kulus umbes neli operatsiooni. Nüüd oli see binaarotsingu halvim juhtum. See näitab, et teostatud toimingute arvu ja massiivi suuruse vahel on logaritmiline seos.

toimingute arv = log (10) = 4 (umbes)

baasi 2 jaoks

Binaarotsingu tulemuse saame üldistada järgmiselt:

Suuruse n massiivi korral on binaarotsingu abil tehtavate toimingute arv: log (n)

Suur O tähis

Eespool toodud lausetes nägime, et massiivi n suuruse korral teostab lineaarne otsing otsingu lõpetamiseks n toimingut. Teiselt poolt tegi binaarotsing log (n) toimingute arvu (mõlemad halvimal juhul). Me võime seda kujutada graafikuna ( x-telg : elementide arv, y-telg : toimingute arv).

Allikas: Techtud

Jooniselt on üsna selge, et lineaarotsingu keerukuse suurenemise kiirus on palju kiirem kui binaarotsingu puhul.

Algoritmi analüüsimisel kasutame selle aja keerukuse tähistamiseks tähistust ja see tähistus on Big O tähistamine.

Näiteks: lineaarotsingu ajalist keerukust saab kahendotsingu korral esitada O (n) ja O (log n) (kus n ja log (n) on toimingute arv).

Allpool on loetletud mõnede populaarsete algoritmide keerukus Ajas või Big O:

  1. Binaarotsing: O (log n)
  2. Lineaarne otsing: O (n)
  3. Kiire sortimine: O (n * log n)
  4. Valiku sortimine: O (n * n)
  5. Reisiv müüja: O (n!)

Järeldus

Hindan väga teie pingutusi, kui loete seda artiklit endiselt. Nüüd peate kindlasti mõtlema - miks on aja keerukust nii oluline mõista?

Me teame, et väikese arvu elementide (näiteks 10) puhul ei ole binaarotsingu ja lineaarse otsingu abil tehtavate toimingute arvu erinevus nii suur. Kuid reaalses maailmas tegeleme enamasti probleemidega, millel on palju andmeid.

Näiteks kui meil on otsimiseks 4 miljardit elementi, siis halvimal juhul võtab lineaarne otsing ülesande täitmiseks 4 miljardit toimingut. Binaarotsing täidab selle ülesande vaid 32 toiminguga. See on suur erinevus. Oletame nüüd, et kui ühe toimingu lõpuleviimiseks kulub 1 ms, võtab binaarotsing aega vaid 32 ms, lineaarne otsing aga 4 miljardit ms (see on umbes 46 päeva). See on oluline erinevus.

See on põhjus, miks aja keerukuse uurimine muutub oluliseks, kui tegemist on nii suure hulga andmetega.

Ressursid

Grokkimise algoritmid - autor Aditya Y Bhargava

CS Dojo sissejuhatus suurde O-tähistusse ja aja keerukusse