РусҚаз

Сложность алгоритма

Информатика · 9 класс · Алгоритмы обработки · Урок 3 из 4

Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Что это

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

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

Зачем это нужно

Современные системы работают с гигантскими объёмами: поисковики просматривают миллиарды страниц, навигаторы в беспилотных машинах за доли секунды перебирают маршруты, а обучение нейросетей в дата-центрах стоит огромных денег на электричество. Если алгоритм квадратичный, на большом объёме он просто не успеет, и никакой суперкомпьютер не спасёт. ИИ может написать работающую программу, но человек, который понимает сложность, сразу увидит, что она развалится на миллионе пользователей, и поставит задачу правильно. Это умение ценят в любой команде, которая делает большие сервисы.

Ночной зал дата-центра, длинные ряды серверных стоек с мигающими огоньками, инженер с ноутбуком смотрит на графики нагрузки.

Как это работает

Мы не засекаем секунды, а считаем, сколько шагов сделает алгоритм в худшем случае, когда объём данных равен эн. Линейный поиск проверяет элементы подряд, поэтому работа растёт вместе с данными. Бинарный поиск каждый раз отбрасывает половину, и удвоение данных добавляет всего одно сравнение. А пузырёк сравнивает почти каждую пару, поэтому данных в десять раз больше — работы в сто раз больше; пока эн маленькое, разницы не видно, но на миллионе элементов она становится пропастью.

Две дороги в горы: по одной пологой тропинке легко идёт путник, другая резко уходит вверх крутой лестницей, и второй путник устало остановился.

Немного истории

Значок «О большое» придумали не программисты, а математики конца девятнадцатого века: его ввёл немецкий математик Пауль Бахман, а широко распространил Эдмунд Ландау. В программирование этот язык принёс Дональд Кнут, автор знаменитой многотомной книги «Искусство программирования», — с тех пор так сравнивают алгоритмы во всём мире.

Учёный в очках и свитере сидит за столом, заваленным рукописями и толстыми книгами, и пишет карандашом в тетради при свете настольной лампы.

Формула: рост работы

Чтобы сравнивать алгоритмы, записывают, как число операций зависит от объёма данных эн. Линейный поиск — о от эн: данных в десять раз больше, и работы в десять раз больше. Бинарный поиск — о от логарифма эн: логарифм по основанию два показывает, сколько раз число можно поделить пополам, поэтому при удвоении данных добавляется всего одно сравнение; точнее, он делает целую часть логарифма по основанию два от эн плюс одно сравнение. Пузырёк — о от эн квадрат: каждый элемент сравнивается почти с каждым, и при росте эн в десять раз работа растёт в сто раз. Здесь эн — количество элементов, безразмерное число, а результат — число операций.

  • 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 — лимит сравнений, —

Что будем делать на практике

А теперь давай попробуем выполнить практическое задание. Перед тобой график: по горизонтали — количество элементов эн, по вертикали — число сравнений, а три линии показывают линейный поиск, бинарный поиск и пузырёк; пунктиром отмечен лимит в тысячу сравнений. Сейчас эн равно десяти: линейный делает десять сравнений, бинарный четыре, а пузырёк сорок пять — пока он легко укладывается. Твоя задача — найти самое большое эн, при котором пузырёк ещё не выходит за тысячу. Составь неравенство эн умножить на эн минус один пополам не больше тысячи, прикинь примерное эн и проверь соседние значения — одно должно уложиться, а следующее уже нет. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.

Задание в опыте

Пузырёк делает n(n − 1)/2 сравнений. Найдите наибольшее n, при котором он уложится в 1000 сравнений.
Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Уроки темы: Алгоритмы обработки

  1. Поиск: линейный и бинарный
  2. Сортировки
  3. Сложность алгоритма
  4. Рекурсия