Что такое сложность алгоритма и зачем нужно O-большое

Представь два способа найти слово в словаре: листать страницы подряд от буквы «А» или открыть примерно посередине и сразу прыгать в нужную половину. Оба работают. Но один справится за пару секунд, а другой заставит тебя стариться над страницами. Вот эту разницу — насколько быстро алгоритм справляется, когда данных становится много — и описывает сложность алгоритма.

Скорость — это не про секундомер

Когда говорят, что один алгоритм «быстрее» другого, легко подумать, что речь о секундах на конкретном компьютере. Но это обманчиво: твой ноутбук и мощный сервер посчитают одно и то же за разное время, да и завтра выйдет железо ещё быстрее. Поэтому программисты измеряют скорость не в секундах, а в количестве шагов, которые алгоритм делает.

И главный вопрос тут не «сколько шагов на 10 элементах», а как растёт число шагов, когда данных становится всё больше. Будет ли алгоритм нормально работать на десяти числах, на тысяче, на миллионе? Именно этот рост и называют сложностью алгоритма. Один алгоритм при росте данных едва замечает прибавку, а другой захлёбывается уже на средних объёмах.

Знакомься: O-большое

Чтобы коротко записать, как растёт число шагов, придумали специальную нотацию — O-большое (по-английски Big O). Внутри скобок пишут формулу от n — количества элементов, которые обрабатывает алгоритм. Это как этикетка скорости: посмотрел на неё — и сразу понял, чего ждать на больших данных.

O-большое нарочно грубое. Его не волнуют мелочи вроде «алгоритм делает 3 шага на каждый элемент или 5». Его волнует только характер роста. Поэтому 5n и 100n для O-большого одинаковы — оба это просто O(n), прямая линия. А вот n и n² — уже принципиально разные миры. Вот самые частые этикетки, от лучшей к худшей:

• O(1) — постоянное время. Число шагов не зависит от объёма данных вообще. Взять первый элемент списка — что в списке из 3 чисел, что из миллиона, это один шаг.
• O(log n) — логарифмическое. С каждым шагом задача уменьшается вдвое. Тот самый трюк со словарём, открытым посередине.
• O(n) — линейное. Шагов столько же, сколько элементов. Прочитать весь список один раз, чтобы найти максимум.
• O(n²) — квадратичное. Для каждого элемента пробегаешь по всем остальным. Растёт пугающе быстро.

Аналогия с поиском друга в толпе

Представь, что ты на огромном концерте и потерял друга. Как его найти?

Способ первый: ты идёшь вдоль рядов и заглядываешь в лицо каждому подряд. Если в зале n человек, в худшем случае придётся проверить всех n. Удвоится толпа — удвоится и твоя работа. Это O(n), честный перебор.

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

Разница между O(n) и O(n²) — это разница между «подождать минуту» и «подождать неделю», стоит данным подрасти.

Прикинь на цифрах: при n = 1000 линейный алгоритм сделает 1000 шагов, а квадратичный — миллион. При n = 1 000 000 линейный сделает миллион, а квадратичный — триллион. Триллион шагов современный компьютер будет жевать заметно, тогда как миллион проскочит мгновенно. Вот почему программисты так дёргаются, увидев в коде вложенный цикл по тем же данным.

Зачем это тебе на самом деле

Можно подумать: «Я пишу маленькие программки, мне-то что». Но сложность — это интуиция, которая спасает в самый неподходящий момент. Твой код отлично работал на 50 тестовых записях, ты выложил его в реальный сервис, пришли 5 миллионов пользователей — и всё повисло. Часто причина именно в том, что где-то спрятался O(n²) там, где можно было сделать O(n) или O(log n).

Тот самый поиск по словарю «открой посередине» называется бинарным поиском и работает за O(log n). Чтобы ты прочувствовал силу логарифма: чтобы найти нужное среди миллиарда отсортированных элементов, бинарному поиску хватит примерно 30 шагов. Тридцати! А линейному перебору в худшем случае понадобился бы миллиард. Именно так поисковики и базы данных мгновенно находят ответ в гигантских хранилищах.

Поэтому O-большое — не занудная теория ради экзамена, а способ заранее, ещё на бумаге, понять, выживет твоя программа под нагрузкой или умрёт. Ты учишься смотреть на алгоритм и спрашивать: «А что будет, когда данных станет в тысячу раз больше?» Тот, кто умеет задавать этот вопрос, пишет программы, которые не разваливаются на росте — а это, по сути, и есть граница между любителем и инженером.