Что такое Big O простыми словами

Разбираем, как программисты оценивают скорость алгоритма без секундомера.

Зачем нужна оценка

Скорость алгоритма нельзя честно мерить секундами: на разных компьютерах цифры разные. Поэтому оценивают иначе — как растёт число действий при увеличении объёма данных. Эту оценку и записывают через Big O. Она отвечает на вопрос «что будет, когда данных станет в сто раз больше».

O(n) и O(n²) на пальцах

O(n) значит, что время растёт пропорционально числу элементов: вдвое больше данных — вдвое дольше. Пример — простой проход по списку. O(n²) хуже: при удвоении данных время вырастает вчетверо. Так ведут себя вложенные циклы, сравнивающие каждый с каждым, — например, пузырьковая сортировка.

Как этим пользоваться

Big O помогает выбрать алгоритм заранее, не запуская программу. Бинарный поиск с его делением пополам куда лучше полного перебора именно по Big O. Новичку не нужна строгая математика — достаточно чувствовать разницу между «растёт медленно» и «растёт взрывообразно».

Частые вопросы

Почему игнорируют константы? Big O показывает характер роста, а не точное время; на больших данных характер важнее множителей.

С чего начать понимать сложность? Сравнить перебор и бинарный поиск на растущих данных. Пошаговую логику удобно ощущать в игре Дрон Кодер.