Python - анализ алгоритмов

Анализ алгоритмов

Эффективность алгоритма можно анализировать на двух разных этапах: до реализации и после реализации. Они следующие -

A Priori Analysis- Это теоретический анализ алгоритма. Эффективность алгоритма измеряется исходя из предположения, что все другие факторы, например скорость процессора, постоянны и не влияют на реализацию.
A Posterior Analysis- Это эмпирический анализ алгоритма. Выбранный алгоритм реализован на языке программирования. Затем это выполняется на целевом компьютере. В этом анализе собирается фактическая статистика, такая как время работы и необходимое пространство.

Сложность алгоритма

Предположим X это алгоритм и n - размер входных данных, время и пространство, используемые алгоритмом X, - два основных фактора, которые определяют эффективность X.

Time Factor - Время измеряется путем подсчета количества ключевых операций, таких как сравнения, в алгоритме сортировки.
Space Factor - Пространство измеряется путем подсчета максимального объема памяти, требуемого алгоритмом.

Сложность алгоритма 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) линейно растет с увеличением размера ввода.