Kas yra O-žymuo (Big O žymuo)?

O-notation (Big O notation) yra būdas apibūdinti algoritmo asimptotinį sudėtingumą, tai yra, kaip vykdymo laikas arba atminties naudojimas auga didėjant įvesties duomenų dydžiui.

Pavyzdžiui, jei algoritmas turi sudėtingumą O(n), tai reiškia, kad vykdymo laikas auga linijiniu būdu su įvesties dydžiu. Jei O(n²), laikas auga proporcingai kvadratui įvesties dydžio.

Pavyzdys Go kalba:

func sum(arr []int) int {
    total := 0
    for _, v := range arr {
        total += v
    }
    return total
}

Funkcija sum turi sudėtingumą O(n), nes pereina per visus masyvo elementus vieną kartą.