Kas ir O-notation (Big O notation)?

O-notation (Big O notation) ir veids, kā aprakstīt algoritma asimptotisko sarežģītību, tas ir, kā izpildes laiks vai atmiņas izmantošana pieaug ar ievades datu lieluma pieaugumu.

Piemēram, ja algoritma sarežģītība ir O(n), tas nozīmē, ka izpildes laiks pieaug lineāri ar ievades lielumu. Ja tas ir O(n²), laiks pieaug proporcionāli kvadrātam no ievades lieluma.

Piemērs Go valodā:

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

Funkcija sum ir O(n) sarežģītības, jo tā vienreiz pārbauda visus masīva elementus.