Учебники

Python — Алгоритм анализа

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

  • Априорный анализ — это теоретический анализ алгоритма. Эффективность алгоритма измеряется в предположении, что все другие факторы, например скорость процессора, являются постоянными и не влияют на реализацию.

  • Апостериорный анализ — это эмпирический анализ алгоритма. Выбранный алгоритм реализован с использованием языка программирования. Затем выполняется на целевом компьютере. В этом анализе собраны фактические статистические данные, такие как время выполнения и требуемое пространство.

Априорный анализ — это теоретический анализ алгоритма. Эффективность алгоритма измеряется в предположении, что все другие факторы, например скорость процессора, являются постоянными и не влияют на реализацию.

Апостериорный анализ — это эмпирический анализ алгоритма. Выбранный алгоритм реализован с использованием языка программирования. Затем выполняется на целевом компьютере. В этом анализе собраны фактические статистические данные, такие как время выполнения и требуемое пространство.

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

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