Kas yra didžiojo O žymėjimas?

Didžiojo O (Big O) notacija yra matematinė žymė, naudojama apibūdinti funkcijos asimptotinį elgesį ir jos viršutinę ribą. Programinės įrangos kūrimo kontekste ji taikoma algoritmų našumo įvertinimui atsižvelgiant į laiką (laiko sudėtingumas) ir atmintį (vietos sudėtingumas) didėjant įvesties duomenų dydžiui. Ji apibūdina blogiausią scenarijų:

Dažniausiai pasitaikančios laiko sudėtingumo klasės:

• O(1): Pastovus laikas. Laiko trukmė nepriklauso nuo įvesties duomenų dydžio:
• O(log n): Logaritminis laikas. Laiko trukmė lėtai auga didėjant įvesties duomenų dydžiui (pavyzdžiui, dvejetainis paieška):
• O(n): Linijinis laikas. Laiko trukmė tiesiogiai proporcinga įvesties duomenų dydžiui (pavyzdžiui, paprasta paieška):
• O(n log n): Linijinis laikas. Dažnai pasitaiko efektyviuose rūšiavimo algoritmuose (pavyzdžiui, greitasis rūšiavimas, susiliejimo rūšiavimas):
• O(n^2): Kvadratinis laikas. Laiko trukmė auga proporcingai kvadratui įvesties duomenų dydžio (pavyzdžiui, burbuliukų rūšiavimas, pasirinkimo rūšiavimas):
• O(2^n): Eksponentinis laikas. Laiko trukmė labai greitai auga didėjant įvesties duomenų dydžiui. Dažnai pasitaiko pilno paieškos užduotyse:

Kodo pavyzdžiai ir jų laiko sudėtingumas:

// O(1)
int firstElement = array[0];

// O(n)
for (int i = 0; i < array.length; i++) {
    // kažkokia operacija
}

// O(n^2)
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        // kažkokia operacija
    }
}

Didžiojo O žymuo sutelkiama į išraiškos dominuojantį narį ir ignoruoja konstantas bei mažiau reikšmingus narius, nes didelių įvesties duomenų atveju jų indėlis tampa nereikšmingas. Pavyzdžiui, algoritmas su sudėtingumu O(2n^2 + 5n + 10) laikomas O(n^2).

Supratimas apie Big O yra svarbus renkantis efektyviausius algoritmus ir duomenų struktūras programavimo metu.