Mis on suur O märgistus?

Big O (Big O) märgistus on matemaatiline märge, mida kasutatakse funktsiooni asümptootilise käitumise ja selle ülemise piiri kirjeldamiseks. Tarkvaraarenduse kontekstis kasutatakse seda algoritmide jõudluse hindamiseks aja (ajukasutuse keerukus) ja mälu (paigutuse keerukus) tarbimise osas, kasvades sisendandmete suurusel. See kirjeldab halvimat stsenaariumi:

Kõige levinumad ajakeerukuse klassid:

• O(1): Püsiv aeg. Täitmisaeg ei sõltu sisendandmete suurusest:
• O(log n): Logaritmiline aeg. Täitmisaeg kasvab aeglaselt sisendandmete suuruse suurenemisel (näiteks binaarotsing):
• O(n): Lineaarne aeg. Täitmisaeg on otseselt proportsionaalne sisendandmete suurusega (näiteks lihtne otsing):
• O(n log n): Lineaarne aeg. Tavaliselt esineb tõhusates sorteerimisalgoritmides (näiteks kiire sorteerimine, ühendamise sorteerimine):
• O(n^2): Kvadraatne aeg. Täitmisaeg kasvab sisendandmete kvadraatkraadiga (näiteks mullisortimine, valiksortimine):
• O(2^n): Eksponentsiaalne aeg. Täitmisaeg kasvab väga kiiresti sisendandmete suuruse suurenemisel. Esineb sageli täieliku otsingu ülesannetes:

Koodinäited ja nende ajakeerukus:

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

// O(n)
for (int i = 0; i < array.length; i++) {
    // mingi operatsioon
}

// O(n^2)
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        // mingi operatsioon
    }
}

Big O märgistus keskendub väljenduse domineerivale liikmele ja ignoreerib konstantseid ning vähem olulisi liikmeid, kuna suurte sisendandmete puhul muutub nende panus vähemoluliseks. Näiteks algoritm, mille keerukus on O(2n^2 + 5n + 10), loetakse O(n^2)-ks.

Big O mõistmine on oluline kõige tõhusamate algoritmide ja andmestruktuuride valimisel programmeerimise ajal.