В прошлой статье я немного затронул тему эффективных и неэффективных алгоритмов. Сейчас же предлагаю разобраться, как правильно оценить код с точки зрения его скорости выполнения.
Прежде всего надо выяснить, что мы понимаем под эффективным алгоритмом. Попробую дать авторское определение: эффективный алгоритм — код, который выполняется с минимальным использованием вычислительных ресурсов процессора. Соответственно, неэффективный алгоритм, наоборот, требует больше ресурсов и, соответственно, больше времени для выполнения.
Давайте рассмотрим, что же такое «хороший» и «плохой» алгоритм, на примере простой задачи с leetcode.
Условие: на вход поступает массив целых чисел. На выходе необходимо вывести массив, в котором все нули расположены в конце, а остальные числа сохраняют свой порядок.
Пример
Вход: 7 0 1 15 0 0 3 9 0 25
Выход: 7 1 15 3 9 25 0 0 0 0
«Плохое решение»
Идея первого решения заключается в том, чтобы последовательно сдвигать каждый ноль по отдельности вправо, пока все нули не окажутся в конце массива.
«Хорошее» решение
В основе второго решения лежит метод двух указателей, в котором nums[i] указывает на ноль. Если nums[j] не указывает на ноль, то значения указателей меняются местами, и нули перемещаются в конец массива.
Измерим время выполнения каждого алгоритма на одинаковых входных данных с помощью встроенной библиотеки timeit. Важно уточнить, что считается среднее время 1 000 000 итераций кода.
Время выполнения первого решения: 0.00000422994859999744 сек.
Время выполнения второго решения: 0.00000132772239999031 сек.
Несмотря на то, что второе решение выполнилось быстрее первого, оба алгоритма работают весьма за оптимальное время. Но что будет, если размер входных данных увеличится в 10^4 раза? Давайте проверим. На этот раз возьмем среднее арифметическое 10 итераций.
Время выполнения первого алгоритма: 84.48735556000028168455 сек.
Время выполнения второго алгоритма: 0.01210930999950505724 сек.
Легко заметить, что при масштабировании входных данных первый алгоритм резко деградировал, а второй всё также сохранил свою эффективность.
Проверять каждый раз эффективность алгоритма, замеряя время выполнения программы, неудобно и не совсем точно. Чтобы избежать лишних сложностей, обратимся к О-большому (Big O Notation). Это математическая нотация, которая помогает определить сложность алгоритма от размера входных данных без необходимости замерять время. О-большим принято оценивать сложность алгоритма в худшем случае. Рассмотрим на примере.
Допустим у нас есть три массива с одинаковым размером. Нужно написать алгоритм, который находит число 256 и выводит YES, если число есть, иначе NO
Входные данные
nums1 = [1, 3, 5, 17, 29, 10, 256]
nums2 = [1, 3, 5, 555, 17, 29, 10]
nums3 = [256, 1, 3, 5, 17, 29, 10]
Анализ трех массивов показывает, что программа с nums1 и nums2 займет больше всего времени и, соответственно, выполнит больше действий, так как искомое число в первом случае находится в конце, а во втором отсутствует. Быстрее всего выполнится код с nums3, так как 256 находится в начале массива.
Вывод: несмотря на то, что скорость выполнения при nums3 быстрее, чем при nums1 или nums2, в общем случае алгоритм описывается по наихудшему сценарию, то есть O(n) — линейная сложность.
Еще один пример квадратичной сложности
- Цикл for работает за O(n)
- Метод remove удаляет элемент из списка за O(n)
Так как метод remove вызывается внутри цикла, общая сложность алгоритма становится O(n²)
Виды сложностей
Рассмотрим существующие виды сложностей, все их можно изобразить на графике
- O(1) — Доступ к элементу массива
- O(log n) — Бинарный поиск
- O(n) — Линейный проход по массиву
- O(n log n) — Быстрая сортировка
- O(n²) — Два вложенных цикла
- O(2^n) — Перебор всех подмножеств множества
Нужно ли оценивать сложность алгоритма на постоянной основе? Это важно, но не всегда необходимо. Нужно понимать, что оценивать сложность алгоритма и оптимизировать надо с умом. Например, если вы пишете код для работы с небольшим количеством данных, можно этим пренебречь. Но если вы разрабатываете высоконагруженный сервис, то без оценки сложности далеко не уедешь.
Если вы интересуетесь темой изучения алгоритмов и структур данных для прохождения собеседования/написания олимпиады, хочу порекомендовать курс «Алгоритмы и структуры данных: курс для профессионалов»
А если вам интересна тема образования, хочу пригласить вас в свой телеграм-канал