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

Сложность алгоритма — порядок зависимости времени и памяти, необходимых для вычисления алгоритма под его размерность. Временная сложность: T(n). Пространственная сложность: O(n) [здесь нужно уточнять, что имеется ввиду под этим выражением, так как оно может обозначать асимптотическое обозначение «О большое», что не относится к определению пространственной сложности].

Сложность сама по себе не позволяет определить ни время, ни необходимый объем памяти, а позволяет лишь оценить увеличение этих показателей по мере роста размерности задачи.

Пример. T(n) = n: при повышении размерности, например, в 5 раз время выполнения возрастает в 5 раз. T(n) = n²: при повышении размерности, например, в 5 раз время выполнения возрастает в 25 раз.

Оценка сложности алгоритма: 1. Подсчитать количество элементарных операций, выполняемых во время работы. 2. В этой зависимости [по результату п. 1] определить максимальный порядок зависимости от размерности.

Алгоритмы одной и той же сложности могут значительно отличаться по времени выполнения.

При таком подходе кодирование облегчается в связи со снятием довольно большой аналитической нагрузки на кодера. В противном случае на относительно простых задачах программист может не справиться с возложенной на него задачей по двум причинам: — некорректное понимание постановки задачи. — недостаточно четкая формулировка критериев приемлемости её решения.

В связи с этим при создании сколь угодно сложного ПО большое внимание уделяется именно разработке максимально подробного технического задания как по всей задаче в целом, так и по каждому фрагменту в частности.

Если количество элементарных операций (FLOP, «флоп») постоянно и не зависит от размерности задачи, то считается, что T(n) = 1.

Время выполнения алгоритма зависит не только от размерности данных, но и от значений этих данных.

Различают три типа сложности: 1. Максимальная сложность (самая неблагоприятная ситуация, когда алгоритм работает медленнее всего; пример — пузырьковая сортировка). 2. Минимальная сложность (самая благоприятная ситуация, когда алгоритм работает быстрее всего). 3. Средняя сложность (для среднестатистического случая).

На практике чаще всего встречаются следующие сложности: 1. T(log n) — на каждом шаге алгоритма выполняется постоянное количество операций, и задача размерности сводится к задаче n/k (т. е. n –> n/k; k – целое положит. число). Пример: двоичный (бинарный) поиск. 2. T(n) — на каждом шаге алгоритма выполняется постоянное количество операций, не зависящее от n, и задача размерности сводится к задаче n-1 (т. е. n –> n-1). Пример: линейный поиск. 3. T(n*log n) — на каждом шаге выполняется количество операций c*n (c – константа), и задача размерности сводится к задаче n/k (т. е. n –> n/k; k – целое положит. число). Примеры: быстрая сортировка (сортировка Хоара), сортировка слиянием, пирамидальная сортировка. 4. T(n²) — при наличии двух вложенных циклов, количество итераций которых прямо пропорционально размерности задачи c*n. Задача размерности сводится к задаче n-1 (т. е. n –> n-1). Примеры: пузырьковая сортировка, сортировка вставками, сортировка выбором.