2.1 Оценка эффективности алгоритмов¶
При проектировании алгоритмов мы последовательно стремимся к двум уровням целей.
- Найти решение задачи: алгоритм должен надежно получать правильный ответ в заданном диапазоне входных данных.
- Найти оптимальное решение: для одной и той же задачи может существовать несколько решений, и нам хочется выбрать максимально эффективный алгоритм.
Иными словами, если задача в принципе решается, эффективность алгоритма становится главным критерием оценки его качества. Она включает два следующих измерения.
- Временная эффективность: сколько времени работает алгоритм.
- Пространственная эффективность: сколько памяти занимает алгоритм.
Короче говоря, наша цель - проектировать структуры данных и алгоритмы, которые "и быстры, и экономны по памяти". Эффективная оценка алгоритмов крайне важна, потому что только так можно сравнивать разные алгоритмы и направлять процесс их проектирования и оптимизации.
Методы оценки эффективности в основном делятся на два типа: практическое тестирование и теоретическая оценка.
2.1.1 Практическое тестирование¶
Предположим, у нас есть алгоритм A и алгоритм B, оба решают одну и ту же задачу, и нам нужно сравнить их эффективность. Самый прямой способ - взять компьютер, запустить оба алгоритма и зафиксировать время работы и объем используемой памяти. Такой способ оценки отражает реальную ситуацию, но имеет и серьезные ограничения.
С одной стороны, трудно исключить влияние факторов тестовой среды. Аппаратная конфигурация влияет на производительность алгоритма. Например, если алгоритм имеет высокий уровень параллелизма, он лучше подходит для многоядерных CPU; если алгоритм интенсивно работает с памятью, он покажет себя лучше на быстрой памяти. Иными словами, результаты тестирования одного и того же алгоритма на разных машинах могут различаться. Это означает, что пришлось бы тестировать на самых разных машинах и усреднять результаты, а на практике это нереалистично.
С другой стороны, полное тестирование требует больших ресурсов. По мере изменения объема входных данных алгоритм может вести себя по-разному. Например, при небольшом объеме входных данных время работы алгоритма A может быть меньше, чем у алгоритма B; но при большом объеме результаты могут оказаться прямо противоположными. Поэтому для убедительных выводов пришлось бы тестировать входные данные множества разных масштабов, а это требует значительных вычислительных ресурсов.
2.1.2 Теоретическая оценка¶
Поскольку практическое тестирование имеет серьезные ограничения, можно попытаться оценить эффективность алгоритма только с помощью вычислений. Такой метод называется асимптотическим анализом сложности (asymptotic complexity analysis), или сокращенно анализом сложности.
Анализ сложности показывает зависимость между временем и пространственными ресурсами, требуемыми алгоритму, и масштабом входных данных. Он описывает тенденцию роста времени и памяти, необходимых алгоритму, по мере увеличения размера входных данных. Это определение звучит немного тяжеловесно, поэтому полезно разложить его на три ключевые идеи.
- "Временные и пространственные ресурсы" соответствуют временной сложности (time complexity) и пространственной сложности (space complexity) соответственно.
- "По мере увеличения размера входных данных" означает, что сложность отражает связь между эффективностью алгоритма и масштабом входа.
- "Тенденция роста времени и пространства" означает, что анализ сложности интересуется не конкретными значениями времени или памяти, а тем, насколько быстро они растут.
Анализ сложности устраняет недостатки практического тестирования, что проявляется в следующих аспектах.
- Для него не нужно реально запускать код, а значит, он экологичнее и экономит ресурсы.
- Он не зависит от тестовой среды, поэтому результаты анализа применимы ко всем платформам выполнения.
- Он позволяет увидеть эффективность алгоритма при разных объемах данных, особенно на больших данных.
Tip
Если понятие сложности пока все еще кажется тебе запутанным, не переживай: мы подробно разберем его в следующих разделах.
Анализ сложности дает нам "линейку" для оценки эффективности алгоритмов, позволяя измерять, сколько времени и памяти требуется для выполнения конкретного алгоритма, и сравнивать эффективность разных алгоритмов между собой.
Сложность - это математическое понятие, поэтому для начинающих оно может показаться довольно абстрактным и сравнительно трудным. С этой точки зрения анализ сложности, возможно, не лучший самый первый материал для знакомства. Однако, когда мы обсуждаем особенности конкретной структуры данных или алгоритма, почти невозможно не затронуть скорость его работы и использование памяти.
В итоге рекомендуется еще до глубокого погружения в структуры данных и алгоритмы сформировать хотя бы первичное понимание анализа сложности, чтобы уметь выполнять анализ сложности простых алгоритмов.