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

Определения и обозначения

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

Размер входных данных — количество элементов или другая величина, описывающая объём данных, которые получает алгоритм. Обычно размер обозначают буквой n; например, для списка из 30 чисел n = 30. Это обозначение помогает выразить число действий общей формулой, а не считать только для одного примера.

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

Линейная и квадратичная сложность описывают разные темпы роста числа шагов. При линейной зависимости число действий пропорционально n, а при квадратичной — n². Например, удвоение n примерно удваивает линейное число действий, но увеличивает квадратичное примерно в четыре раза.

Как это устроено

Время выполнения на одном компьютере не всегда позволяет честно сравнить два алгоритма. Устройства могут работать с разной скоростью, а одна и та же задача может быть реализована по-разному. Поэтому рассматривают, как меняется количество действий при росте входных данных: эта зависимость сохраняет смысл даже при смене компьютера. Для предварительной оценки достаточно понять характер роста, не измеряя секунды.

Сначала определяют, какой показатель описывает размер входа. Для списка обычно берут количество его элементов и обозначают его n; для других задач это может быть, например, число записей. Затем находят действия, количество которых меняется вместе с этим размером. Если операция выполняется фиксированное число раз, независимо от n, она не объясняет рост вычислений при увеличении данных.

В последовательном алгоритме одна часть выполняется после другой. Поэтому число действий этих частей складывают: если первая выполняет n действий, а вторая — 2n, всего получается n + 2n = 3n. Цикл устроен иначе: его тело повторяется, и каждое повторение добавляет новые действия. Значит, при подсчёте нужно учитывать не только команды внутри тела, но и количество повторений.

Вложенный цикл повторяется внутри другого цикла. Если внешний цикл проходит n раз, а внутренний при каждом проходе тоже выполняется n раз, внутреннее действие выполняется n × n = n² раз. Причина в том, что для каждого из n проходов внешнего цикла заново происходят все n проходов внутреннего. Поэтому нельзя считать такой алгоритм как один цикл из n повторений.

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

Рост числа действий алгоритма с увеличением размера данных

Сначала найдите размер входа n, затем определите, сколько раз выполняется действие, которое нужно посчитать. Для последовательных частей числа действий складывают, а для вложенных циклов — учитывают повторение внутреннего цикла при каждом проходе внешнего. Сравнение значений при разных n показывает, насколько быстро растёт объём вычислений.

Разбор задач

Задача 1. Алгоритм выполняет одно и то же действие для каждого из n элементов списка. Нужно выразить число повторений через n и определить характер роста. Здесь важно не умножать число действий на что-то ещё: каждое выполнение цикла соответствует одному элементу.

1. В списке n элементов, значит, цикл проходит по каждому из них.
2. Для каждого элемента действие выполняется один раз, поэтому всего оно повторится n раз.
3. Число повторений пропорционально n, следовательно, рост линейный.

Ответ: n выполнений действия; линейный рост.

Задача 2. Первый цикл выполняется n раз, второй — 2n раз; циклы идут последовательно, а не один внутри другого. Требуется найти общее число выполнений тел циклов и оценить рост. Поскольку завершение первого цикла предшествует началу второго, количество действий нужно сложить.

1. В первом цикле тело выполняется n раз.
2. Во втором цикле тело выполняется 2n раз.
3. Всего получаем n + 2n = 3n выполнений; множитель 3 не меняет линейный характер роста.

Ответ: 3n выполнений тел циклов; линейный рост.

Задача 3. Алгоритм сравнивает пары элементов двумя вложенными циклами, каждый выполняется n раз. Нужно определить число сравнений при n = 20 и выяснить, как оно изменится при удвоении n. Так как внутренний цикл запускается при каждом проходе внешнего, числа повторений здесь перемножаются.

1. При n = 20 внешний цикл выполняется 20 раз, а внутренний при каждом таком проходе — ещё 20 раз.
2. Число сравнений равно 20 × 20 = 400.
3. При удвоении размера каждый цикл выполняется 40 раз, поэтому сравнений будет 40 × 40 = 1600, то есть в четыре раза больше.

Ответ: при n = 20 выполняется 400 сравнений; при удвоении n их число увеличивается в четыре раза, до 1600.

Типичные ошибки

Считать сложность только по времени на конкретном компьютере — значит смешивать свойства алгоритма со скоростью устройства и особенностями реализации. Такую оценку часто выбирают потому, что время удобно измерить, но оно может измениться при запуске на другом компьютере. Для сравнения сначала смотрите на рост числа действий относительно n. Проверьте себя: сможете ли вы описать зависимость, не называя секунды?

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

Для вложенных циклов нельзя просто сложить числа повторений внешнего и внутреннего циклов. Так ошибаются, когда воспринимают оба цикла как последовательные, хотя внутренний запускается заново при каждом проходе внешнего. Если циклы вложены, посчитайте число повторов внутреннего действия для одного прохода внешнего и умножьте на число проходов внешнего. При n повторениях каждого цикла результатом будет n × n, а не 2n.

Одинаковое число действий на маленьком входе не означает, что алгоритмы будут одинаково эффективны при любом размере данных. На небольших примерах различие между n и n² может быть неочевидным, поэтому легко недооценить его. Подставьте в зависимости два размера, например 10 и 100, и сравните результаты. Если один показатель растёт гораздо быстрее, на больших данных различие станет существенным.

Связь с другими темами

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

Оценка сложности помогает выбирать алгоритмы для сортировки, поиска и обработки больших наборов данных. Для небольшой задачи два способа могут казаться одинаково удобными, но на большом объёме один из них способен потребовать намного больше вычислений. Поэтому оценка роста полезна до того, как алгоритм применят к большому набору данных.

Что запомнить

• Сложность показывает, как растёт объём вычислений при увеличении входных данных.
• Размер входных данных обычно обозначают буквой n.
• Один цикл из n повторений даёт линейный рост числа действий.
• Два вложенных цикла по n повторений могут дать n² действий.
• Для последовательных частей алгоритма числа действий складывают.
• Для вложенных циклов числа повторений перемножают.
• При больших объёмах данных важен характер роста числа действий.