58. Понятие алгоритма. Методы оценки алгоритмической сложности.

Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата

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

Следует иметь в виду, что существует несколько оценок сложности алгоритма.

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

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

Емкостная сложность — асимптотическая оценка числа одновременно существующих скалярных величин при выполнении алгоритма на входных данных длиною п.

Структурная сложность — характеристика количества управляющих структур в алгоритме и специфики их взаиморасположения.

Когнитивная сложность — характеристика доступности алгоритма для понимания специалистами прикладных областей.

Тип цикла (for, while, repeat) не влияет на сложность. Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью. Вложенность повторений является основным фактором роста сложности. В качестве примера приведем сложности хорошо известных алгоритмов поиска и сортировки для массива размером п:

O(n) — линейная сложность

Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.

O(log n) — логарифмическая сложность

Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log nэлементов.

O(n²) — квадратичная сложность

Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n, т. е. n².