Анализ алгоритмов для начинающих: вводное руководство
Введение в анализ алгоритмов для программистов и сочувствующих. Разбираемся в базовых понятиях теоретической информатики.
Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:
- углубишься в решение практических задач;
- узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.
Ты также будешь на связи с преподавателем и другими студентами.
В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂
Вы никогда не задумывались, для чего нужна теоретическая computer science, и какое отношение она имеет к реальному программированию? Кажется, что если вас не очень интересует сфера математического анализа, то TCS может понадобиться только для ответа на вопросы о сложности алгоритмов на собеседованиях. Должно же быть нечто большее!
Хороший программист создает удобное и полезное программное обеспечение, а очень хороший старается сделать его максимально эффективным в использовании. Для этого необходимо понимать, почему и в каких пределах работает программа.
Вспомните фильм Каратэ-пацан с Джеки Чаном и Джейден Смит. Джеки заставляет Дре снова и снова надевать и снимать куртку. Смысл этого действия не в одежде, а в приобретении необходимых для кунг-фу навыков.
То же самое делает для нас теоретическая computer science. Она закладывает прочную основу фундаментальных абстрактных понятий, благодаря которой мы можем принимать правильные практические решения.
Эта статья предназначена для программистов, которые хорошо разбираются в написании кода, но не в TCS. Чтобы понять изложенные концепции, не требуется глубокое знание математики. Мы начнем с самых основ: алгоритмов, их вычислительной сложности, тета-нотации, асимптотического поведения и пессимистического анализа.
Что такое алгоритм?
Алгоритм можно определить как список шагов, которые необходимо выполнить для решения задачи.
Допустим, вы хотите купить книгу в интернете. Алгоритм ваших действий будет следующим:
КупитьКнигу (названиеКниги) {
Открыть Amazon
Искать книгу по названию
Если товар в наличии, добавить его в корзину
Оформить заказ
С нетерпением ждать отправки
}
Купить Книгу ("В тихом омуте")
Анализ алгоритмов и производительность
Анализ алгоритмов можно определить как теоретическое исследование производительности компьютерных программ и использования ими ресурсов.
Мы сосредоточимся на производительности.
Прежде всего, подумайте, есть ли в программировании что-то более важное, чем производительность? Разумеется! Если сверхбыстрая программа выдает неверный результат, это плохая программа.
Еще есть такие понятия, как простота, удобство обслуживания, надежность, безопасность, функциональность и удобство для пользователя. Все они гораздо важнее производительности.
Вот например, Эван Шпигель решил перепроектировать Snapchat. Зачем? Snapchat уже работает отлично, как было задумано. Просто пользователи жаловались на определенную сложность работы с приложением, и Эван решил сделать его проще в использовании. Удобство явно перевешивает эффективность алгоритмов.
Очевидно, что производительность – это не самая важная вещь. Тогда почему мы о ней говорим?
Дело в том, что иногда удобство использования напрямую связано с производительностью.
Представьте, что вы смотрите на веб-страницу, которая загружается уже целую вечность. В режиме реального времени недостаточно быстрое приложение считается неработающим. Слишком большое использование памяти тоже ухудшает пользовательский опыт.
Анализ алгоритмов на практике
Вооружившись этими знаниями, попробуем проанализировать простую задачу сортировки.
Мы будем использовать алгоритм сортировки пузырьком. На псевдокоде он выглядит вот так:
Bubblesort( var a as array )
for i from 1 to N
for j from 0 to N - i
if a[j] > a[j + 1]
swap( a[j], a[j + 1] )
end func
Функция Bubblesort принимает неупорядоченный массив чисел в виде входного параметра и сортирует его.
Давайте рассмотрим работу функции на реальном примере. Отправим на вход следующие данные: {6, 5, 3}. На выходе мы ожидаем получить {3, 5, 6}, то есть массив, отсортированный по возрастанию. Будем последовательно сравнивать числа и при необходимости менять их местами (swap).
Проход 1
• Сравниваем первый и второй элементы:
{**6, 5**, 3}
• 6 > 5, поэтому их следует поменять:
{5, 6, 3}
• Сравниваем второй и третий элементы:
{5, **6, 3**}
• 6 > 3, меняем их местами:
{5, 3, 6}
После первого прохода наш массив выглядит так:
{5, 3, 6}
Он все еще не отсортирован, алгоритм нужно повторить.
Проход 2
• Сравниваем первый и второй элементы:
{**5, 3**, 6}
• 5 > 3, меняем:
{3, 5, 6}
• Сравниваем второй и третий элементы:
{3, **5, 6**}
• 5 < 6, здесь все правильно.
{3, 5, 6}
После второго прохода мы получили желаемый результат.
Больше узнать о сортировке пузырьком вы можете здесь.
Время работы
Время выполнения алгоритма напрямую зависит от входных данных:
• от их качества
Предположим, что исходный список {3, 5, 6}, переданный алгоритму пузырьковой сортировки, уже упорядочен. В этом случае достаточно сделать один проход по нему, чтобы убедиться в правильности расположения элементов. Но, что делать, если входной список {6, 5, 3} отсортирован в обратном порядке? Потребуется несколько раундов выполнения, чтобы получить желаемый результат, так как нужно заменить каждый элемент.
• от количества
Представьте себе сортировку списка, содержащего 6*10⁹ элементов. Вероятно, она будет выполняться чуть дольше, чем упорядочивание шести чисел.
Итак, когда мы делаем анализ алгоритмов по времени выполнения, то обычно определяем максимальный предел. Эта верхняя граница дает гарантию пользователю, что выполнение задачи не займет больше конкретного количества секунд.
Количество проходов
Также имеет значение, сколько раз придется повторить алгоритм для выполнения задачи. Например, для пузырьковой сортировки можно подсчитать количество выполненных сравнений.
Чаще всего анализ проводится для худшего случая, при котором придется сделать больше всего повторений. В нашем примере худшим случаем является массив, упорядоченный по убыванию.
Гораздо реже рассматривается средний случай для всех возможных входных данных. Это наиболее полезная мера, но рассчитать ее очень сложно.
Можно также выполнять анализ алгоритмов для лучшего случая входных данных, но практического приложения это не имеет. Если массив чисел уже упорядочен, нет особого смысла сортировать его.
Асимптотический анализ алгоритмов
Итак, давайте попробуем проанализировать худший случай сортировки пузырьком и формально измерить, насколько быстро она работает.
Но где именно мы должны запустить этот алгоритм? На чьем компьютере? А ведь если запустить его на суперкомпьютере, он будет работать очень-очень быстро!
Нам явно требуется некий инструмент для сравнения двух алгоритмов на уровне идеи без учета деталей реализации: языка программирования, аппаратного обеспечения и т. д.
Начинается самое интересное: асимптотический анализ алгоритмов!
Этот метод игнорирует все константы, зависящие от машины, и вместо конкретной величины времени выполнения, рассматривает его динамическое изменение.
Для представления временной сложности алгоритмов в основном используют три асимптотических нотации:
- Θ-нотация (нотация тета большое);
- O-нотация (нотация о большое);
- Ω-нотация (нотация омега большое).
Θ-нотация
Давайте взглянем на нотацию тета большое. Она следует простым двум правилам:
- отбросить слагаемые низких порядков;
- отбросить константы.
Что это значит, рассмотрим на примере:
3n³ + 40n² - 10n + 409
Первое правило гласит: отбросьте слагаемые низких порядков. Здесь самый высокий порядок n – это 3. Следовательно все остальное, включая свободный член 409, можно отбросить.
3n³
Второе правило требует отбросить константы. Убираем 3 и получаем в итоге:
n³
Что читается как тета большое от n в кубе.
Это инженерный способ манипулирования тета-нотацией.
Функция n³, которую мы помещаем в Θ – это сложность нашего алгоритма.
Когда n приближается к бесконечности, алгоритм Θ(n²) всегда будет работать быстрее, чем Θ(n³). Неважно, какими были члены нижнего порядка или ведущие константы. Даже если вы запустите Θ(n²) на медленном компьютере, а Θ(n³) – на быстром, с ростом n первый будет все сильнее вырываться вперед.
Анализ алгоритмов заботится только о том, во сколько раз чаще выполняется операция по мере увеличения входных данных, что соответствует поведению в худшем случае. Если alg1 превосходит alg2 для очень большого входящего n, очевидно, что он будет делать это и при малом n. Учитывая это, мы можем отбросить все медленнорастущие слагаемые и сконцентрироваться только на самых быстрорастущих. Это называется асимптотическим поведением.
Нотация о большое работает с худшими случаями, а омега большое – с лучшими.
Перевод статьи Shilpa Jain: The Ultimate Beginners Guide To Analysis of Algorithm