Что такое O-нотация (Big O notation)?

O-нотация (Big O notation) — это способ описания асимптотической оценки сложности алгоритма, то есть того, как время выполнения или использование памяти растёт с увеличением размера входных данных.

Например, если алгоритм имеет сложность O(n), это значит, что время выполнения растёт линейно с размером входа. Если O(n²) — время растёт пропорционально квадрату размера входа.

Пример на Go:

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

Функция sum имеет сложность O(n), так как перебирает все элементы массива один раз.