Асимптотическая сложность

Зачем нужна формальная оценка

Замер времени на конкретной машине ненадёжен: результат зависит от процессора, кэша и нагрузки. Нужна машинно-независимая мера — количество операций как функция от размера входа n.

O-нотация

O(f(n)) описывает верхнюю границу роста: алгоритм выполнит не более c·f(n) операций при достаточно большом n.

Рост при увеличении n:

Θ и Ω

• Ω(f(n)) — нижняя граница: алгоритм выполнит не менее c·f(n) операций.
• Θ(f(n)) — точная оценка: нижняя и верхняя граница совпадают.

На практике используют O — как оценку в худшем случае.

Примеры в Go

// O(1)
x := nums[i]

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

// O(n²)
for i := range nums {
    for j := i + 1; j < len(nums); j++ {
        if nums[i] > nums[j] {
            nums[i], nums[j] = nums[j], nums[i]
        }
    }
}

Упражнения