Mis on O-märge (Big O märge)?

O-notation (Big O notation) on viis kirjeldada algoritmi asümptootilist keerukust, see tähendab, kuidas täitmiskiirus või mälu kasutus kasvab sisendandmete suuruse suurenedes.

Näiteks, kui algoritmi keerukus on O(n), siis tähendab see, et täitmiskiirus kasvab lineaarselt sisendi suurusega. Kui see on O(n²), siis kasvab aeg sisendi suuruse ruutena.

Näide Go keeles:

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

Funktsioon sum on O(n) keerukusega, kuna see läbib kõik massiivi elemendid ühe korra.