Big O нотация на пальцах: Почему ваш код — это велосипед, а не ракета

Big O нотация на пальцах: Почему ваш код - это велосипед, а не ракета

Представьте, что вы пришли на кухню. Вам нужно пожарить 10 котлет. На сковороду влезает только 2 штуки, а время жарки одной стороны - 5 минут. Как бы вы ни крутили, вы потратите одно и то же время.

А теперь представьте, что котлет 1000. Или миллион. Вот тут-то и появляется главный вопрос программиста: Как изменится время работы, если данных станет сильно больше?

Этот вопрос и решает Big O нотация (читается «О большое»). Это не магия, это просто способ сказать: «Слушай, когда у меня будет миллион пользователей, этот код ляжет или пролетит как пуля?»

Давайте разберем самые популярные классы скорости - от мечты программиста до настоящего «пожарного ада».

O(1) - «Мгновенно. Всегда. Даже на печке»

Это константная сложность. Задача решается за одно и то же время, даже если у вас в базе 1 запись или 100 миллиардов.

Пример: Достать элемент из массива по индексу. `arr[5]` - компьютер просто берет адрес и прыгает в память. Котлета там одна или тысяча - ему все равно.

Бытовой пример: Открыть страницу книги на 42-й странице. Вы просто смотрите на номер, а не ищете по каждой странице.

O(log n) - «Быстро. Очень. Очень быстро»

Логарифмическая сложность. Рост данных почти не замедляет работу. Добавили в 1000 раз больше данных? Скорость упадет всего в 10 раз.

Где встречается: Бинарный поиск. Открываете телефонную книгу на середине, смотрите: «Б» или «Я»? И каждый раз отбрасываете половину.

Код для понимания:

python

def binary_search(arr, target):

low, high = 0, len(arr)-1

while low <= high:

mid = (low+high)//2

if arr[mid] == target:

return mid

elif arr[mid] < target:

low = mid+1 # Отбрасываем левую половину

else:

high = mid-1 # Отбрасываем правую половину

return -1

Даже среди миллиарда записей вам нужно не больше 30 шагов (потому что 2^30 = 1 миллиард).

O(n) - «Линейно. Котлета за котлетой»

Линейная сложность. Как жарить котлеты по одной. Время растет прямо пропорционально количеству данных.

Пример: Поиск самого большого числа в неотсортированном списке. Компьютер вынужден посмотреть на каждую котлету.

python

def find_max(arr):

max_val = arr[0]

for num in arr: # Один проход по всем элементам

if num > max_val:

max_val = num

return max_val

100 элементов - 100 операций. Миллион - миллион операций. Честно и предсказуемо.

O(n²) - «Пора пить кофе. Долгий кофе»

Квадратичная сложность. Это когда у вас есть список, и вы для каждого элемента пробегаете еще раз по каждому элементу.

Классическая ловушка новичка: Поиск дубликатов двойным циклом.

python

def find_duplicates(arr):

for i in range(len(arr)):

for j in range(i+1, len(arr)): # Вложенный цикл!

if arr[i] == arr[j]:

print("Дубликат!")

10 элементов - 100 операций (терпимо).

1000 элементов - 1 миллион операций (тормозит).

1 000 000 элементов - 1 триллион операций (ваш сервер превратился в каменный уголь).

Бытовой пример: Вы на вечеринке. Чтобы поздороваться с каждым, вы подходите к каждому лично. А потом вам кажется, что забыли руку - и начинаете заново. Потом еще раз. Это O(n²).

O(2^n) - «Выключите это. Пожалуйста»

Экспоненциальная сложность. Чуть-чуть добавили данных - время взлетает до бесконечности мгновенно.

Где бывает Рекурсивное вычисление чисел Фибоначчи «в лоб», задача о сумме подмножеств.

python

def fib_recursive(n):

if n <= 1:

return n

return fib_recursive(n-1) + fib_recursive(n-2)

n=40 - это уже миллионы вызовов. n=100 - вы умрете, а код все еще будет работать.

Главная таблица для запоминания (мем)

| Скорость | Название | Пример | Для 1 млн элементов |

|:---:|:---|:---|:---:|

| O(1) | Константа | Доступ по индексу | 1 операция |

| O(log n) | Логарифм | Бинарный поиск | ~20 операций |

| O(n) | Линейная | Поиск без индекса | 1 млн |

| O(n²) | Квадрат | Пузырьковая сортировка | 1 трлн |

| O(2^n) | Экспонента | Рекурсия Фибоначчи | Бесконечность |

Как это применяется на собеседованиях

Забудьте про слова «быстро» и «медленно». Технический лидер задает вопрос:

«Какова time complexity твоего решения?»

Если вы написали вложенный цикл там, где нужен был один проход (O(n²) вместо `O(n)`), вам вежливо улыбнутся и попросят подумать еще.

Если вы использовали хэш-таблицу для поиска вместо массива (O(1) против O(n)), вы, скорее всего, прошли этот этап.

Главный вывод (запомните на всю жизнь)

Big O не про «миллисекунды». Это про «форму смерти» вашего кода при масштабировании.

Можно написать функцию, которая сортирует 100 элементов за 0.001 секунды на пузырьке. И с гордостью залить в прод. А через месяц придет миллион элементов - и сервер упадет.

Поэтому еще на этапе дизайна спросите себя: «А что произойдет, если n станет равно миллиарду?»

Если ответ «Мой компьютер вспыхнет» - значит, вы где-то пропустили O(n²). И пора доставать бинарный поиск.