Что такое Big O нотация

Big O нотация описывает производительность алгоритма в худшем случае, показывая, как растёт время выполнения или использование памяти при увеличении размера входных данных.

Примеры:

• O(1) – константное время (доступ к элементу массива по индексу)

arr := [3]int{1, 2, 3}
val := arr[0] // O(1)

• O(n) – линейная сложность (поиск в неотсортированном массиве)

for _, num := range arr { // O(n)
    if num == target {
        return true
    }
}

• O(n²) – квадратичная сложность (вложенные циклы)

for i := 0; i < n; i++ { // O(n²)
    for j := 0; j < n; j++ {
        // ...
    }
}

Используется для сравнения алгоритмов и выбора оптимального решения.