Mi az az O-jelölés (Big O jelölés)?

Az O-jelölés (Big O jelölés) egy módszer az algoritmus aszimptotikus komplexitásának leírására, vagyis arra, hogy a futási idő vagy a memóriahasználat hogyan növekszik a bemeneti adatok méretének növekedésével.

Például, ha egy algoritmus komplexitása O(n), akkor ez azt jelenti, hogy a futási idő lineárisan növekszik a bemeneti mérettel. Ha O(n²), akkor a futási idő a bemeneti méret négyzetével arányosan növekszik.

Példa Go nyelven:

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

A sum függvény komplexitása O(n), mivel egyszer végigmegy az összes elemén a tömbnek.