Algoritmai ir sudėtingumas: praktiniai klausimai su paaiškinimais

1Ką matuoja sudėtingumas

Algoritmas yra baigtinis tikslių žingsnių sąrašas, sprendžiantis uždavinį, pavyzdžiui, rūšiuojantis sąrašą ar ieškantis pavardės telefonų knygoje.

Du algoritmai gali spręsti tą patį uždavinį, bet užtrukti labai skirtingai. Sudėtingumas aprašo, kaip darbas auga, kai didėja įvestis.

Įvesties dydis žymimas n: rūšiuojamų elementų skaičius, sąrašo ilgis, grafo mazgų skaičius.

Įsivaizduokite, kad ieškote pavardės 1000 puslapių telefonų knygoje. Skaitant kiekvieną puslapį prireikia iki 1000 žingsnių. Atsiverčiant per vidurį ir kaskart perpus mažinant – apie 10 žingsnių.

Laiko sudėtingumas skaičiuoja žingsnius. Atminties sudėtingumas skaičiuoja papildomą atmintį. Abu užrašomi kaip n funkcija.

Dažniausiai nagrinėjamas blogiausias atvejis: daugiausia darbo iš visų n dydžio įvesčių. Kartais užduodamas vidutinis arba geriausias atvejis.

2O didysis ir augimo klasės

O didysis žymėjimas palieka tik tai, kas svarbu dideliems n. Atmetate pastoviuosius daugiklius ir paliekate tik greičiausiai augantį narį.

Kai n = 1000, n² narys yra 3 000 000, o 5n – vos 5000. Mažesni nariai beveik nekeičia sumos.

Šios klasės kartojasi nuolat, nuo lėčiausio iki greičiausio augimo:

• O(1), pastovus: masyvo elemento skaitymas pagal indeksą.
• O(log n), logaritminis: dvejetainė paieška, kuri kiekvienu žingsniu perpus sumažina uždavinį.
• O(n), tiesinis: vienas perėjimas per visus elementus, pavyzdžiui, didžiausios reikšmės paieška.
• O(n log n): geri rūšiavimo algoritmai, pavyzdžiui, rūšiavimas sujungimu.
• O(n²), kvadratinis: du įdėtiniai ciklai per elementus, pavyzdžiui, burbulo rūšiavimas.
• O(2ⁿ), eksponentinis: išbandomas kiekvienas poaibis. Greitai tampa netinkamas naudoti.

O didysis yra viršutinė riba: darbas auga ne greičiau nei taip. Ω (omega didžioji) yra apatinė riba, o Θ (teta didžioji) yra tiksli riba, ir viršutinė, ir apatinė.

Logaritmo pagrindas O didžiajame nesvarbus, nes skirtingų pagrindų logaritmai skiriasi tik pastoviu daugikliu.

3Paieška, rūšiavimas ir rekursija

Keli algoritmai pasitaiko beveik kiekviename kurse. Jų sudėtingumą išmokite kaip faktus.

• Tiesinė paieška tikrina elementus po vieną: O(n). Dvejetainei paieškai reikia surūšiuoto masyvo ir ji kiekvienu žingsniu perpus sumažina intervalą: O(log n).
• Burbulo, įterpimo ir išrinkimo rūšiavimas lygina ir keičia elementus įdėtiniuose cikluose: O(n²). Įterpimo rūšiavimas jau surūšiuotam masyvui yra O(n).
• Rūšiavimas sujungimu padalija masyvą pusiau, surūšiuoja puses ir sujungia: O(n log n) visais atvejais, su O(n) papildomos atminties.
• Greitasis rūšiavimas dalija aplink atramos elementą: vidutiniškai O(n log n), bet blogiausiu atveju O(n²), pavyzdžiui, surūšiuotam masyvui, kai atrama pasirenkamas pirmas elementas.
• Joks rūšiavimas, kuris tik lygina elementus, blogiausiu atveju negali būti geresnis nei Ω(n log n). Skaičiavimo rūšiavimas greitesnis, nes nelygina.

Rekursinė funkcija kviečia pati save su mažesne įvestimi, kol pasiekia baziniu atveju, į kurį atsako tiesiogiai. Jos veikimo laikas užrašomas kaip rekurentinė lygtis:

• T(n) = T(n/2) + O(1) duoda O(log n), kaip dvejetainė paieška.
• T(n) = 2T(n/2) + O(n) duoda O(n log n), kaip rūšiavimas sujungimu.
• T(n) = T(n − 1) + O(n) duoda O(n²).
• T(n) = 2T(n − 1) + O(1) duoda O(2ⁿ).

Verta žinoti tris projektavimo idėjas. Skaidyk ir valdyk padalija, išsprendžia ir sujungia. Godusis kiekvienu žingsniu renkasi lokaliai geriausią variantą. Dinaminis programavimas išsaugo persidengiančių dalinių uždavinių atsakymus, kad jie būtų skaičiuojami vieną kartą.

4Metodas žingsnis po žingsnio

Kaip rasti kodo fragmento laiko sudėtingumą:

1. Nuspręskite, kas yra n: įvesties dydis.
2. Suskaičiuokite, kiek kartų vyksta kiekvienas ciklas. Ciklas, kuris kaskart didėja 1, vyksta maždaug n kartų. Ciklas, kuris dvigubėja ar dalijasi pusiau, vyksta maždaug log₂ n kartų.
3. Vienas į kitą įdėti ciklai dauginasi. Vienas po kito einantys ciklai sudedami.
4. Rekursinei funkcijai užrašykite rekurentinę lygtį: kiek kreipinių, kokio dydžio, plius darbas per kreipinį.
5. Palikite greičiausiai augantį narį ir atmeskite konstantas.
6. Patikrinkite su mažu skaičiumi, pavyzdžiui, n = 8 arba n = 1024.

Teorijos klausimui pirmiausia įvardykite algoritmą ar idėją, kurią jis aprašo, tada prisiminkite jo sudėtingumą ir sąlygas (surūšiuota įvestis, neneigiami svoriai, persidengiantys daliniai uždaviniai).

5Išspręstas pavyzdys

Sekite kiekvieną žingsnį. Pabandykite nuspėti kitą, prieš jį atidarydami.

6Dažnos klaidos

• Dauginami vienas po kito einantys ciklai. n + n = 2n vis tiek yra O(n).
• Paliekamos konstantos, pavyzdžiui, O(2n) arba O(n/2). Abu yra O(n).
• Dvigubėjantis ciklas laikomas vykstančiu n kartų. Jis vyksta maždaug log₂ n kartų.
• Dvejetainė paieška naudojama nesurūšiuotiems duomenims arba susietajam sąrašui, kuriame vidurio negalima pasiekti vienu žingsniu.
• Pateikiamas greitojo rūšiavimo vidutinis atvejis, kai klausiama apie blogiausią.
• Manoma, kad O didysis reiškia „tiksliai“. O(n²) yra viršutinė riba; Θ(n²) yra tikslus augimas.

7Kaip atrodo egzamino uždaviniai

• Lengvi: pagrindinės sąvokos ir faktai. Dvejetainės paieškos, rūšiavimo sujungimu ar masyvo elemento pasiekimo sudėtingumas, O, Ω ir Θ reikšmė, kas yra rekursija.
• Vidutiniai: sąvokų taikymas. Kodo fragmento sudėtingumas, sprendžiama rekurentinė lygtis, kaip kinta laikas padvigubinus n, koks algoritmas tinka užduočiai.
• Sunkūs: atvejai ir analizė. Pagrindinė teorema, greitojo rūšiavimo blogiausi atvejai, godusis algoritmas ir dinaminis programavimas, klasės P, NP ir NP-pilnosios.

P apima uždavinius, kuriuos galima išspręsti per polinominį laiką. NP apima uždavinius, kurių sprendinius galima patikrinti per polinominį laiką. Kiekvienas P uždavinys yra NP; ar P = NP, vis dar nežinoma.