Ką matuoja Big-O
Šiame kurse nekursi naujos programos kiekvienai temai. Kursi vieną — savo medijų biblioteką — ir kiekviena pamoka pridės jai vieną komandą. Iki 15 pamokos turėsi įrankį, kuris rikiuoja, indeksuoja ir randa duomenis keliolika skirtingų būdų, ir žinosi, kuris būdas kada laimi.
Pasirink temą dabar ir laikykis jos: muzika, filmai, žaidimai ar knygos. Toliau tekste sakysim „įrašas" — tu galvok apie dainą, filmą ar knygą.
Ką iš tikrųjų matuoja Big-O
Big-O nematuoja sekundžių. Jis matuoja, kaip auga darbas, kai auga duomenų kiekis — kiek papildomų veiksmų kainuoja kiekvienas naujas įrašas.
Trys dydžiai, kuriuos sutiksi jau šioje pamokoje:
| Žymėjimas | Ką reiškia | Pavyzdys |
|---|---|---|
| O(1) | darbas nepriklauso nuo n | paimti elementą pagal indeksą |
| O(log n) | n padvigubėja — darbas padidėja per vieną žingsnį | dvejetainė paieška (6 pamoka) |
| O(n) | darbas auga tiesiogiai su n | peržiūrėti visą sąrašą |
Šioje pamokoje realizuosi tiesinę paiešką — O(n). Ji nėra bloga; ji yra atskaitos taškas. Kiekviena struktūra, kurią statysi vėliau, bus lyginama su šiuo skaičiumi.
Geriausias, vidutinis ir blogiausias atvejis
Tiesinė paieška tūkstančio įrašų bibliotekoje:
- geriausias atvejis — ieškomas įrašas yra pirmas: 1 palyginimas;
- blogiausias atvejis — jis yra paskutinis arba jo apskritai nėra: 1000 palyginimų;
- vidutinis atvejis — maždaug n/2.
Big-O kalba apie blogiausią atvejį, nebent pasakyta kitaip. Todėl tiesinė paieška yra O(n), nors kartais pataiko iš pirmo karto.
Ką pastatysi šioje pamokoje
Keturis dalykus, ta tvarka:
Item— įrašo tipas. Du jo laukai turi rėžius, ir tai ne atsitiktinumas.metrics.Counter— matavimo įrankis. Vienintelis kodas, kurį gauni gatavą.algo gen— duomenų generatorius. Be jo neturi ką matuoti.algo find— tiesinė paieška su skaitikliu. Pirmasis matavimas.