Что это
Сложность алгоритма — это ответ на вопрос: во сколько раз больше придётся работать, если данных станет больше. Представь, что ищешь друга в списке класса и в списке всего города: один способ поиска почти не замедлится, а другой растянется на часы. Сложность и показывает, как ведёт себя алгоритм, когда задача растёт.
Зачем это нужно
Современные системы работают с гигантскими объёмами: поисковики просматривают миллиарды страниц, навигаторы в беспилотных машинах за доли секунды перебирают маршруты, а обучение нейросетей в дата-центрах стоит огромных денег на электричество. Если алгоритм квадратичный, на большом объёме он просто не успеет, и никакой суперкомпьютер не спасёт. ИИ может написать работающую программу, но человек, который понимает сложность, сразу увидит, что она развалится на миллионе пользователей, и поставит задачу правильно. Это умение ценят в любой команде, которая делает большие сервисы.
Как это работает
Мы не засекаем секунды, а считаем, сколько шагов сделает алгоритм в худшем случае, когда объём данных равен эн. Линейный поиск проверяет элементы подряд, поэтому работа растёт вместе с данными. Бинарный поиск каждый раз отбрасывает половину, и удвоение данных добавляет всего одно сравнение. А пузырёк сравнивает почти каждую пару, поэтому данных в десять раз больше — работы в сто раз больше; пока эн маленькое, разницы не видно, но на миллионе элементов она становится пропастью.
Немного истории
Значок «О большое» придумали не программисты, а математики конца девятнадцатого века: его ввёл немецкий математик Пауль Бахман, а широко распространил Эдмунд Ландау. В программирование этот язык принёс Дональд Кнут, автор знаменитой многотомной книги «Искусство программирования», — с тех пор так сравнивают алгоритмы во всём мире.
Формула: рост работы
Чтобы сравнивать алгоритмы, записывают, как число операций зависит от объёма данных эн. Линейный поиск — о от эн: данных в десять раз больше, и работы в десять раз больше. Бинарный поиск — о от логарифма эн: логарифм по основанию два показывает, сколько раз число можно поделить пополам, поэтому при удвоении данных добавляется всего одно сравнение; точнее, он делает целую часть логарифма по основанию два от эн плюс одно сравнение. Пузырёк — о от эн квадрат: каждый элемент сравнивается почти с каждым, и при росте эн в десять раз работа растёт в сто раз. Здесь эн — количество элементов, безразмерное число, а результат — число операций.
O(n), O(log n), O(n²)n — количество элементов данных, —
O — порядок роста числа операций в худшем случае, —бинарный поиск: ⌊log₂ n⌋ + 1 сравненийn — количество элементов, —
log₂ n — сколько раз n можно поделить пополам, —
Формула: число сравнений
Почему пузырёк делает эн умножить на эн минус один, делённое на два сравнения? Первый проход сравнивает эн минус одну пару соседей, следующий на одну меньше, потом ещё на одну, и так до одной пары. Если сложить эту лесенку, получится ровно эн умножить на эн минус один пополам — столько же, сколько всего пар можно составить из эн элементов. Буква эн — количество элементов, ответ — число сравнений, оба безразмерные. Если эн увеличить вдвое, сравнений станет примерно вчетверо больше, потому что эн здесь фактически стоит в квадрате. Чтобы проверить, уложится ли пузырёк в лимит, составляют неравенство: эн умножить на эн минус один пополам не больше тысячи.
сравнений = n(n − 1)/2n — количество элементов в списке, —n(n − 1)/2 ≤ 1000n — количество элементов, —
1000 — лимит сравнений, —
Что будем делать на практике
А теперь давай попробуем выполнить практическое задание. Перед тобой график: по горизонтали — количество элементов эн, по вертикали — число сравнений, а три линии показывают линейный поиск, бинарный поиск и пузырёк; пунктиром отмечен лимит в тысячу сравнений. Сейчас эн равно десяти: линейный делает десять сравнений, бинарный четыре, а пузырёк сорок пять — пока он легко укладывается. Твоя задача — найти самое большое эн, при котором пузырёк ещё не выходит за тысячу. Составь неравенство эн умножить на эн минус один пополам не больше тысячи, прикинь примерное эн и проверь соседние значения — одно должно уложиться, а следующее уже нет. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.