Перейти к основному содержимому

O-нотация (Big O)

O-нотация (Big O) описывает худший сценарий (или верхнюю границу) того, как будет расти время выполнения алгоритма при увеличении объема входных данных ($n$).

1. O(1) — Константное время (Мгновенно)​

Время выполнения не зависит от количества элементов. Алгоритм выполняет фиксированное количество операций, будь то для 10 элементов или для 10 миллионов.

Примеры в Go:

  • Определение того, четное ли число страниц в книге.
  • Доступ к элементу слайса по индексу (arr[5]).
  • Чтение или запись в map (в среднем случае).
  • Получение длины слайса len(arr).
func getFirstElement(arr[]int) int {
    if len(arr) == 0 {
        return 0
    }
    // O(1): Процессор сразу вычисляет адрес памяти первого элемента
    return arr[0] 
}

2. O(log n) — Логарифмическое время (Очень быстро)​

На каждом шаге алгоритм отсекает половину оставшихся элементов. Время растет очень медленно. Например, для 1 000 000 элементов потребуется всего около 20 шагов.

Примеры в Go:

  • Бинарный поиск (Binary Search) по отсортированному слайсу.
  • Поиск в бинарном дереве поиска (BST).
  • Поиск слова в бумажном словаре (Как ты ищешь слово "Кот"? Ты открываешь словарь примерно посередине. Видишь букву "П". Понимаешь, что "К" левее, и отбрасываешь половину словаря. Снова открываешь середину левой части и так далее. Даже в словаре из 100 000 слов ты найдешь нужное всего за ~17 шагов.)
// O(log n): Бинарный поиск
func binarySearch(arr[]int, target int) bool {
    low, high := 0, len(arr)-1

    for low <= high {
        mid := low + (high-low)/2
        
        if arr[mid] == target {
            return true
        } else if arr[mid] < target {
            low = mid + 1 // Отсекаем левую половину
        } else {
            high = mid - 1 // Отсекаем правую половину
        }
    }
    return false
}

3. O(n) — Линейное время (Нормально)​

Время выполнения растет прямо пропорционально количеству элементов. Если данных в 10 раз больше, алгоритм будет работать в 10 раз дольше. Нам нужно "потрогать" каждый элемент.

Примеры в Go:

  • Простой перебор (цикл for по всему слайсу).
  • Поиск минимума/максимума в неотсортированном массиве.
  • Подсчет суммы всех элементов.
  • Чтение книги от корки до корки или ручной пересчет стопки купюр (Тебе нужно прочитать каждую страницу. Если книга в 2 раза толще, ты потратишь на чтение ровно в 2 раза больше времени. Зависимость прямая)
// O(n): Линейный поиск
func findMax(arr []int) int {
    max := arr[0]
    for _, val := range arr { // Проходим по каждому элементу ровно один раз
        if val > max {
            max = val
        }
    }
    return max
}

4. O(n log n) — Линейно-логарифмическое время (Хорошо для сортировки)​

Это комбинация $O(n)$ и $O(\log n)$. Обычно означает, что алгоритм делит задачу на части (как логарифм), а затем выполняет линейную работу для объединения этих частей. Это лучшее достижимое время для алгоритмов сортировки на основе сравнений.

Примеры в Go:

  • Встроенная сортировка слайсов (slices.Sort(arr) или sort.Ints(arr)).
  • Алгоритмы сортировки: Merge Sort, Quick Sort (в среднем случае), Heap Sort.
  • Сортировка колоды карт (или стопки контрольных работ) по мастям и возрастанию (Ты не можешь сделать это за один проход (O(n)) Обычно ты сначала раскладываешь карты на 4 кучки по мастям (делишь задачу, это логарифмическая часть), а затем быстро сортируешь каждую кучку (линейная работа). Это самый оптимальный способ для человека и для компьютера.)
import "slices"

func sortData(arr[]int) {
    // Внутри Go использует алгоритм pdqsort (Pattern-Defeating Quicksort)
    // Его сложность в худшем/среднем случае — O(n log n)
    slices.Sort(arr) 
}

5. O(n²) — Квадратичное время (Медленно)​

Время выполнения растет в квадрате от количества элементов. Если данных стало в 10 раз больше, время работы увеличится в 100 раз. Обычно возникает при использовании вложенных циклов. Подходит только для небольших объемов данных.

Примеры в Go:

  • Два вложенных цикла по одному и тому же массиву.
  • Наивные алгоритмы сортировки (Сортировка пузырьком, Сортировка выбором).
  • Рукопожатия всех со всеми в комнате
// O(n^2): Сортировка пузырьком
func bubbleSort(arr[]int) {
    n := len(arr)
    // Внешний цикл (n раз)
    for i := 0; i < n; i++ {
        // Внутренний цикл (n раз)
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

6. O(2ⁿ) — Экспоненциальное время (Почти нереально для больших данных)​

С каждым новым добавленным элементом время выполнения удваивается. Алгоритм "взрывается" даже на небольших данных ($n = 30$ уже может считаться вечность). Обычно это полный перебор всех возможных комбинаций.

Примеры в Go:

  • Вычисление чисел Фибоначчи через наивную рекурсию.
  • Перебор всех подмножеств множества.
  • Взлом кодового замка на чемодане (подбор пароля)
// O(2^n): Наивная рекурсия Фибоначчи
func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    // Каждый вызов порождает ДВА новых вызова (дерево разрастается)
    return fibonacci(n-1) + fibonacci(n-2) 
}

Как чинить: Такие задачи обычно решаются с помощью Мемоизации (кэширования) или Динамического программирования, что позволяет свести сложность к $O(n)$.

График роста​

Представь, что $n = 1000$:

  • $O(1)$ = 1 операция.
  • $O(\log n)$ ≈ 10 операций.
  • $O(n)$ = 1 000 операций.
  • $O(n \log n)$ ≈ 10 000 операций.
  • $O(n^2)$ = 1 000 000 операций (миллион).
  • $O(2^n)$ = Число с 300 нулями (больше атомов во Вселенной).