O notacija
O notacija, dar angliškai sakoma "Big O notation" - tai toksai duomenų apdirbimo sudėtingumo vertinimas, paremtas tuo, kaip auga apdirbimui reikalingi resursai, lyginant su apdirbamų duomenų kiekiu. Apdirbimui reikalingi resursai gali būti ir operacinės atminties kiekiai, ir procesoriaus ciklai.
Tokia notacija naudojama, kai reikia pasakyti, kiek sudėtinga bus kažkokius duomenis apdirbti.
- O(1) Fiksuotas laikas, praktikoje tai reiškia, kad duomenys išvis neapdirbami, o tik registruojamas duomenų paketas.
- O(log n) logaritminis laikas, kas reiškia, kad duomenų kiekiui didėjant, laiko sąnaudos didėja gana nežymiai. Tai būdinga duomenims, kurių pradinei daliai reikia daug skaičiavimų, tačiau vėlesni skaičiavimai auga labai nežymiai.
- O(n) Tiesinis laikas, kas reiškia, kad algoritmo laiko sąnaudos auga proporcingai duomenų kiekiui. Tai tipiška paprastiems aritmetiniams algoritmams, nedarantiems duomenų apibendrinimų.
- O(n log n) Kvazi-tiesinis laikas, kas reiškia, kad nors laiko sąnaudos auga netiesiškai, bet visvien gan lėtai. Tai būna aukšto efektyvumo paieškos, rūšiavimo ir pan algoritmuose.
- O(n²) Kvadratinis laikas, kas reiškia, kad didėjant duomenims, laikas auga kaip duomenų kvadratas, t.y., algoritmas sparčiai lėtėja. Tai būdinga atvejams, kur daromas nuoseklus duomenų apibendrinimas.
- O(2ⁿ) Eksponentinis laikas, kas reiškia, kad sunaudojamas laikas didėja eksponentiškai, dėl ko dideli duomenų kiekiai apdirbami labai lėtai. Atvejai, kur reikia atlikti gilesnes analizes.
- O(n!) Faktorialinis laikas, kas reiškia, kad netgi prie nelabai didelių duomenų setų sunaudojimamas laikas pasidaro labai didelis. Jums nepasisekė.
Tokie duomenų apdirbimo algoritmų vertinimai būna aktualūs, kai dirbama su Big Data, nes nuo to neretai priklauso ir Big Data apibrėžimas - pvz., kartais, jei apdirbimas vyksta pagal O(n) sąnaudas, tai duomenys gali būti apdirbami, tačiau jei tie patys duomenys bus apdirbami su O(n²) sąnaudomis, jų apdirbimas gali pasidaryti nebeįmanomas ir gali tekti ieškoti kokių nors netrivialių būdų.
Tai beje, čia dar ne visus blogiausius atvejus aprašėm, nes būna, kad sąnaudos dar labiau didėja. Čia kai po kokius nors Ramsey Theory reikalus pasižiūri, tai paaiškėja, kad net ir kelios dešimtys elementų jau gali būti Big Data...