§ 9–10. Поговорим об эффективности

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

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

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

Время выполнения — время или число элементарных действий, необходимых алгоритму для получения результата. Элементарным действием условно считают простую операцию, например сравнение двух чисел. Подсчёт действий позволяет сравнить алгоритмы независимо от того, насколько быстро работает конкретный компьютер.

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

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

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

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

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

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

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

Как оценивать эффективность алгоритма

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

Разбор задач

Сложение обычным способом и повторным прибавлением единицы

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

1. В способе со столбиком достаточно сложить единицы: 8 + 5 = 13. Если учитывать перенос разряда, требуется ещё записать результат в разрядах, но число операций остаётся небольшим.
2. Во втором способе нужно выполнить пять отдельных прибавлений: 8 → 9 → 10 → 11 → 12 → 13. Здесь число прибавлений равно добавляемому числу.
3. Сравним на более крупном примере, например 8 + 500. Прибавлять единицу придётся 500 раз, а обычное сложение по-прежнему требует действий с разрядами чисел. Значит, повторение становится всё менее выгодным.

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

Поиск числа в упорядоченном списке

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

1. При последовательном поиске начинаем с первого элемента и двигаемся дальше, пока не найдём 42. В худшем случае придётся проверить все 16 элементов.
2. При поиске делением пополам проверяем средний элемент. Если он меньше 42, все элементы левее тоже меньше искомого числа, поэтому их можно отбросить; если больше — отбрасываем правую половину.
3. Повторяем проверку середины оставшейся части. После каждого шага список возможных мест примерно вдвое короче, поэтому для 16 элементов достаточно около четырёх проверок, если середина делится без остатка.

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

Проверка списка на повторяющиеся значения

Условие: нужно выяснить, есть ли в списке одинаковые значения. Можно сравнить каждый элемент с каждым следующим или просматривать список и сохранять уже встреченные значения. Сравним эти способы по действиям и памяти.

1. При попарной проверке для каждого элемента просматриваем все элементы после него. Например, в списке из 5 значений получаем 4 + 3 + 2 + 1 = 10 сравнений, если повтор обнаружен лишь в конце или его нет.
2. При последовательном просмотре проверяем, встречалось ли очередное значение раньше, и затем запоминаем его. Если для проверки удобно использовать отдельный набор уже встреченных значений, повтор можно заметить сразу после появления.
3. Сопоставим затраты: попарный способ хранит мало дополнительных сведений, но может выполнить много сравнений. Способ с запоминанием способен сократить поиск повторов, однако набор занимает дополнительную память.

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

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

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

Нельзя сравнивать алгоритмы на разных входных данных: разницу может вызвать размер или состав данных, а не сам способ решения. Иногда забывают зафиксировать одинаковые условия проверки. Запустите оба алгоритма на одном и том же наборе и только потом сопоставляйте результаты.

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

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

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

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

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

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

• Разные алгоритмы могут решать одну и ту же задачу.
• Алгоритм должен быть не только правильным, но и приемлемым по затратам ресурсов.
• Для сравнения нужно рассматривать одинаковые входные данные.
• Важные ресурсы — время выполнения и память.
• На маленьких данных различия между алгоритмами могут быть незаметны.
• Эффективность оценивают с учётом условий задачи.