Didelis O žymėjimas paaiškintas pavyzdžiais

„Big O“ žymėjimas yra būdas apibūdinti tam tikro algoritmo greitį ar sudėtingumą. Jei jūsų dabartiniam projektui reikalingas iš anksto nustatytas algoritmas, svarbu suprasti, koks greitas ar lėtas jis yra, palyginti su kitomis galimybėmis.

Kas yra „Big O“ žymėjimas ir kaip jis veikia?

Paprasčiau tariant, Big O žymėjimas nurodo, kiek operacijų atliks algoritmas. Jis gauna savo vardą iš pažodinio „Didžiojo O“ prieš numatomą operacijų skaičių.

Ko „Big O“ žymėjimas jums nesako, yra algoritmo greitis sekundėmis. Yra per daug veiksnių, turinčių įtakos algoritmo veikimo laikui. Vietoj to, naudosite „Big O“ žymėjimą, kad palygintumėte skirtingus algoritmus pagal jų atliktų operacijų skaičių.

„Big O“ nustato blogiausio atvejo bėgimo laiką

Įsivaizduokite, kad esate mokytoja su studente, vardu Jane. Norite rasti jos įrašus, todėl naudodamiesi paprastu paieškos algoritmu pereikite savo mokyklos rajono duomenų bazę.

Jūs žinote, kad norint atlikti paprastą paiešką reikia O (n) kartų. Tai reiškia, kad blogiausiu atveju turėsite ieškoti kiekviename įraše (kurį žymi n), kad rastumėte Jane's.

Bet atlikdami paprastą paiešką pastebite, kad Džeinės įrašai yra pats pirmasis įrašas duomenų bazėje. Jums nereikia žiūrėti į kiekvieną įrašą - jį radote bandydami pirmą kartą.

Ar šis algoritmas užtruko O (n) laiką? Arba užtruko O (1) laiko, nes pirmą kartą bandei rasti Jane įrašus?

Šiuo atveju 0 (1) yra geriausias scenarijus - jums pasisekė, kad Jane įrašai buvo viršuje. Tačiau „Big O“ žymėjimas sutelktas į blogiausią scenarijų, kuris yra 0 (n) paprastai paieškai. Tai yra patikinimas, kad paprasta paieška niekada nebus lėtesnė nei O (n) laikas.

Algoritmo veikimo laikas auga skirtingu greičiu

Tarkime, kad norint patikrinti kiekvieną mokyklos rajono duomenų bazės elementą reikia 1 milisekundės.

Naudojant paprastą paiešką, jei turite patikrinti 10 įrašų, reikės 10 ms. Bet naudodami dvejetainio paieškos algoritmą turite patikrinti tik 3 elementus, kurių vykdymas trunka 3 ms.

Daugeliu atvejų sąraše ar duomenų bazėje, kurios reikia ieškoti, bus šimtai ar tūkstančiai elementų.

Jei elementų yra 1 milijardas, paprasta paieška užtruks iki 1 milijardo ms arba 11 dienų. Kita vertus, naudojant dvejetainę paiešką blogiausiu atveju užtruksite vos 32 ms:

Aišku, paprastos paieškos ir dvejetainės paieškos vykdymo laikas neauga beveik tokiu pačiu greičiu. Didėjant įrašų sąrašui, norint atlikti dvejetainę paiešką reikia šiek tiek daugiau laiko. Paprastos paieškos vykdymo laikas auga eksponentiškai, nes ilgėja įrašų sąrašas.

Štai kodėl labai svarbu žinoti, kaip bėgimo laikas didėja, palyginti su sąrašo dydžiu. Būtent čia „Big O“ žymėjimas yra toks naudingas.

Didelis O žymėjimas rodo operacijų skaičių

Kaip minėta pirmiau, Didelės O žymėjimas nerodo laiką algoritmas veiks. Vietoj to, jis rodo atliktų operacijų skaičių. Tai nurodo, kaip greitai auga algoritmas, ir leidžia jį palyginti su kitais.

Čia yra keletas įprastų algoritmų ir jų vykdymo trukmės „Big O“ žymėjime:

Didelis O žymėjimas Algoritmo pavyzdys
O (log n) Dvejetainė paieška
O (n) Paprasta paieška
O (n * log n) „Quicksort“
O (n2) Pasirinkimo rūšiavimas
O (n!) Keliaujantis pardavėjas

Dabar jūs žinote pakankamai, kad būtumėte pavojingi naudodami „Big O“ žymėjimą. Išeik ten ir pradėk lyginti algoritmus.