O-işarəsi (Big O-işarəsi) nədir?

O-notation (Big O notation) algoritmanın zaman ve yaddaş kompleksliyinin giriş məlumatlarının ölçüsünün artması ilə necə böyüdüyünü təsvir etmək üçün istifadə olunan bir yoldur.

Məsələn, əgər bir algoritmanın mürəkkəbliyi O(n) isə, bu, icra vaxtının giriş ölçüsü ilə doğrusal artdığını göstərir. Əgər O(n²) isə, vaxt giriş ölçüsünün kvadratına proporsional olaraq artır.

Go dilində nümunə:

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

sum funksiyasının mürəkkəbliyi O(n)-dir, çünki o, bütün elementləri bir dəfə keçir.