При теоретическом анализе алгоритмов принято оценивать их сложность в асимптотическом смысле, т. Е. Оценивать функцию сложности для произвольно больших входных данных. Термин «анализ алгоритмов» был придуман Дональдом Кнутом.
Алгоритм анализа является важной частью теории вычислительной сложности, которая обеспечивает теоретическую оценку необходимых ресурсов алгоритма для решения конкретной вычислительной задачи. Большинство алгоритмов предназначены для работы с входами произвольной длины. Анализ алгоритмов — это определение количества временных и пространственных ресурсов, необходимых для его выполнения.
Обычно эффективность или время выполнения алгоритма указывается как функция, связывающая длину ввода с числом шагов, известных как временная сложность , или объем памяти, известный как пространственная сложность .
Необходимость анализа
В этой главе мы обсудим необходимость анализа алгоритмов и способы выбора лучшего алгоритма для конкретной задачи, поскольку одна вычислительная задача может быть решена различными алгоритмами.
Рассматривая алгоритм для конкретной задачи, мы можем начать развивать распознавание образов, чтобы с помощью этого алгоритма можно было решать похожие проблемы.
Алгоритмы часто сильно отличаются друг от друга, хотя цель этих алгоритмов одна и та же. Например, мы знаем, что набор чисел может быть отсортирован с использованием разных алгоритмов. Количество сравнений, выполненных одним алгоритмом, может отличаться от других для одного и того же ввода. Следовательно, временная сложность этих алгоритмов может отличаться. В то же время нам необходимо рассчитать объем памяти, необходимый для каждого алгоритма.
Анализ алгоритма — это процесс анализа способности алгоритма решать задачи с точки зрения требуемого времени и размера (объема памяти для хранения при реализации). Однако основной проблемой анализа алгоритмов является требуемое время или производительность. Как правило, мы выполняем следующие виды анализа —
-
В худшем случае — максимальное количество шагов, предпринятых для любого экземпляра размера a .
-
Наилучший вариант — минимальное количество шагов, предпринимаемых для любого экземпляра размера a .
-
Средний случай — среднее количество шагов, предпринятых для любого экземпляра размера a .
-
Амортизация — последовательность операций, применяемая к усредненному по времени вводу размера.
В худшем случае — максимальное количество шагов, предпринятых для любого экземпляра размера a .
Наилучший вариант — минимальное количество шагов, предпринимаемых для любого экземпляра размера a .
Средний случай — среднее количество шагов, предпринятых для любого экземпляра размера a .
Амортизация — последовательность операций, применяемая к усредненному по времени вводу размера.
Чтобы решить проблему, мы должны учитывать время и сложность пространства, так как программа может работать в системе, где память ограничена, но имеется достаточно места или может быть наоборот. В этом контексте, если мы сравниваем сортировку пузырьков и сортировку слиянием . Пузырьковая сортировка не требует дополнительной памяти, но сортировка слиянием требует дополнительного пространства. Хотя временная сложность пузырьковой сортировки выше по сравнению с сортировкой слиянием, нам может потребоваться применить пузырьковую сортировку, если программа должна работать в среде, где память очень ограничена.