Эффективность алгоритма может быть проанализирована на двух разных этапах, до реализации и после реализации. Они следующие —
-
Априорный анализ — это теоретический анализ алгоритма. Эффективность алгоритма измеряется в предположении, что все другие факторы, например скорость процессора, являются постоянными и не влияют на реализацию.
-
Апостериорный анализ — это эмпирический анализ алгоритма. Выбранный алгоритм реализован с использованием языка программирования. Затем выполняется на целевом компьютере. В этом анализе собраны фактические статистические данные, такие как время выполнения и требуемое пространство.
Априорный анализ — это теоретический анализ алгоритма. Эффективность алгоритма измеряется в предположении, что все другие факторы, например скорость процессора, являются постоянными и не влияют на реализацию.
Апостериорный анализ — это эмпирический анализ алгоритма. Выбранный алгоритм реализован с использованием языка программирования. Затем выполняется на целевом компьютере. В этом анализе собраны фактические статистические данные, такие как время выполнения и требуемое пространство.
Сложность алгоритма
Предположим, что X является алгоритмом, а n является размером входных данных, время и пространство, используемое алгоритмом X, являются двумя основными факторами, которые определяют эффективность X.
-
Фактор времени — Время измеряется путем подсчета количества ключевых операций, таких как сравнения, в алгоритме сортировки.
-
Коэффициент пространства — пространство измеряется путем подсчета максимального объема памяти, требуемого алгоритмом.
Фактор времени — Время измеряется путем подсчета количества ключевых операций, таких как сравнения, в алгоритме сортировки.
Коэффициент пространства — пространство измеряется путем подсчета максимального объема памяти, требуемого алгоритмом.
Сложность алгоритма f (n) дает время выполнения и / или объем памяти, требуемый алгоритмом, в терминах n в качестве размера входных данных.
Космическая сложность
Пространственная сложность алгоритма представляет собой объем памяти, необходимый алгоритму в его жизненном цикле. Пространство, требуемое алгоритмом, равно сумме следующих двух компонентов:
-
Фиксированная часть, представляющая собой пространство, необходимое для хранения определенных данных и переменных, которые не зависят от размера проблемы. Например, используемые простые переменные и константы, размер программы и т. Д.
-
Переменная часть — это пространство, необходимое для переменных, размер которых зависит от размера задачи. Например, динамическое выделение памяти, пространство стека рекурсии и т. Д.
Фиксированная часть, представляющая собой пространство, необходимое для хранения определенных данных и переменных, которые не зависят от размера проблемы. Например, используемые простые переменные и константы, размер программы и т. Д.
Переменная часть — это пространство, необходимое для переменных, размер которых зависит от размера задачи. Например, динамическое выделение памяти, пространство стека рекурсии и т. Д.
Пространственная сложность S (P) любого алгоритма P равна S (P) = C + SP (I), где C — фиксированная часть, а S (I) — переменная часть алгоритма, которая зависит от характеристики экземпляра I. простой пример, который пытается объяснить концепцию —
Algorithm: SUM(A, B) Step 1 - START Step 2 - C ← A + B + 10 Step 3 - Stop
Здесь у нас есть три переменные A, B и C и одна константа. Следовательно, S (P) = 1 + 3. Теперь пространство зависит от типов данных заданных переменных и типов констант, и оно будет соответственно умножено.
Сложность времени
Временная сложность алгоритма представляет собой количество времени, которое требуется алгоритму для выполнения до завершения. Требования ко времени могут быть определены как числовая функция T (n), где T (n) может быть измерено как количество шагов, при условии, что каждый шаг потребляет постоянное время.
Например, сложение двух n-битных целых чисел занимает n шагов. Следовательно, общее время вычислений равно T (n) = c ∗ n, где c — время, необходимое для сложения двух битов. Здесь мы видим, что T (n) растет линейно с увеличением размера ввода.