Сложность алгоритмов: O(n), O(log n), O(n²) на пальцах

Когда разработчик говорит, что алгоритм работает за O(n log n) — это не мистика и не математика для гениев.
Это просто способ выразить, насколько быстро (или медленно) алгоритм ведёт себя при росте объёма данных.

🧮 Что такое "O" вообще?​


Это Big O Notation — обозначение асимптотической сложности. Оно показывает, как изменяется время работы или количество операций при росте входных данных n.

💡 Важно: Big O не даёт точного времени, только порядок роста.

Пример:
O(n) = "если данных в 2 раза больше, то и времени нужно в 2 раза больше".


🔹 O(1) — константное время​

  • Пример: получить элемент массива по индексу — arr[5]
  • Сколько бы ни было данных, операция всегда занимает одинаковое время
  • Быстро, стабильно, идеально
✅ Пример на Python:

Python: 
arr = [3, 8, 13, 21]
x = arr[2]  # O(1)

✅ Пример на C:

C: 
int arr[] = {3, 8, 13, 21};
int x = arr[2];  // O(1)


🔹 O(log n) — логарифмическое время​

  • Делим задачу пополам каждый раз
  • Часто встречается в двоичном поиске, деревьях, оптимизированных алгоритмах
  • Очень хорошо масштабируется!
✅ Пример: найти элемент в отсортированном массиве двоичным поиском.

Python: 
# O(log n)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

🔍 Если элементов 1 000 000 — двоичный поиск сделает максимум 20 шагов.

Это логарифм по основанию 2:
Алгоритм двоичного поиска на каждом шаге делит массив пополам. Количество шагов, нужных чтобы "сжать" диапазон до одного элемента — это:
Код: 
максимальное количество шагов=log₂(n)+1

Где:
  • n — количество элементов,
  • log₂(n) — логарифм по основанию 2 (то есть: сколько раз можно делить на 2).

🔢 Пример: n = 1 000 000​

log⁡2(1 000 000)≈19.93

Добавляем 1 (последний шаг сравнения) → округляем до целого: будет 20.

📊 Табличка: для наглядности​

Кол-во элементов: nlog₂nШагов
101
10≈ 3.34
1000≈ 9.9610
1 000 000≈ 19.9320
1 000 000 000≈ 29.930


🔸 O( n ) — линейное время​

  • Простой перебор: от начала до конца
  • Хуже, чем log n, но иногда — единственный способ
  • Часто встречается в задачах на поиск, фильтрацию, подсчёт

✅ Пример:

Python: 
# O(n)
def contains(arr, target):
    for x in arr:
        if x == target:
            return True
    return False

📦 Если данных в 10 раз больше — будет 10 раз больше операций.


⚠️ O(n²) — квадратичное время​

  • Каждый элемент сравнивается с каждым
  • Работает медленно при большом объёме
  • Встречается в пузырьковой сортировке, наивных реализациях
✅ Пример на C — сортировка пузырьком:

C: 
void bubble_sort(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

📉 1000 элементов → миллион сравнений.


📎 Вывод​

  • Понимание сложности — фундамент любой алгоритмики
  • Не всегда нужен самый быстрый алгоритм — главное: подходящий по задаче
  • Если можешь улучшить O(n²) до O(n log n) — делай это!

💬 Вопрос к читателю: какой алгоритм у тебя был настолько неэффективный, что ты его потом переписал с нуля? Делись примерами 👇