Оценка сложности алгоритма

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

Свойства алгоритмов

1. Дискретность (алгоритм должен представлять решение задачи как последовательность некоторых простых шагов)
2. Детерминированность (алгоритм должен в каждый конкретный момент времени однозначно определять следующий шаг исходя из состояния системы)
3. Понятность (алгоритм должен включать только те команды, которые исполнитель может выполнить)
4. Конечность (алгоритм при корректных входных данных должен заканчиваться и выдавать результат)
5. Универсальность (алгоритм должен быть применим к разным наборам входных данных)
6. Результативность (алгоритм должен завершаться с каким-то результатом)

Рассмотрим задачу: дан массив из N чисел, необходимо среди них отыскать заданное число A, при нахождении такового – выдать результат в виде номера позиции, на которой он находится в массиве, в противном случае вывести соответствующее сообщение.

Решить такую задачу можно простым способом: последовательно пройтись по всем элементам массива и сравнить их с числом A. Однако если массив является упорядоченным, то есть каждый следующий элемент больше (меньше) предыдущего, то можно применить другой алгоритм. Предположим, что массив является возрастающим. Тогда для поиска заданного элемента необходимо произвести следующие действия:

1. Найти элемент, стоящий в центре массива, поделить массив на две части относительно этого элемента
2. Сравнить его с заданным числом A
3. Если центральный элемент меньше А, то продолжить поиск в правой части массива, иначе в левой.

Такой алгоритм будет называться алгоритмом половинного деления или дихотомии

Важно знать, какой из алгоритмов будет более эффективным. Этим вопросом занимается теория сложности алгоритмов.

Сложностью алгоритма называется величина T(n), где n – размер задачи. 
Например, в задаче поиска элемента в массиве размерности N размер задачи будет равен N.

Проанализируем приведенные выше алгоритмы. В первом случае для поиска нужного элемента мы последовательно сравниваем по два элемента массива, стоящих подряд, поэтому для нахождения нужного элемента в худшем случае потребуется N-1 сравнений. В этом случае T(n) = n-1. 

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

Оценим теперь, какое количество шагов необходимо для выполнения алгоритма половинного деления. Заметим, что после одного шага размер массива уменьшится в 2 раза, после 2х шагов – в 4 раза, после трех – в 8, после n шагов – в 2n раз. Получается, что для поиска одного элемента в массиве размера N необходимо в худшем случае уменьшить этот массив в N раз, тогда число шагов, необходимое для этого, будет равно log2N.

Очевидно, что второй алгоритм будет выполняться быстрее первого, так как для нахождения элемента в массиве длиной, например, 1000000, в первом случае надо будет потратить приблизительно 1000000 шагов, а во втором – всего около 20.
Однако, для того, чтобы применять

Рассмотрим еще один важный алгоритм – алгоритм сортировки. Предположим, что у нас есть задача – отсортировать неупорядоченный массив чисел по возрастанию. Для этого можно применить простейший алгоритм сортировки – «пузырьковую» сортировку.

Массив можно упорядочить, если последовательно менять местами элементы стоящие «неправильно», то есть не в той последовательности. Сравнивать числа можно как с левого конца массива, так и с правого. Предположим, что мы сравниваем элементы с правого конца массива, тогда можно предложить следующий алгоритм:

Сравним выбранный i-й элемент массива с i-1 элементом. Если   i-1 элемент больше, то меняем их местами, иначе оставляем нетронутыми.

Продолжаем процесс для i от N до 2.

Повторяем пункты 1 и 2 N раз.

После того, как мы выполним пункты 1 и 2 в первый раз, в начале массива окажется наименьший его элемент. Повторяя процесс, мы получим полностью отсортированный массив.

Можно заметить, что нет смысла каждый раз сравнивать все элементы, так как после первого прохода массива в начале окажется наименьший элемент, после второго – 2 наименьших, и так далее. В модифицированном виде алгоритм можно записать так:

for i:=2 to N do

for j:=N downto i do

if Arr[j-1]>Arr[j] then

begin

Tmp:=Arr[j];

Arr[j]:=Arr[j-1];

Arr[j-1]:=Tmp;

end;

Такой алгоритм будет делать (N-1)+(N-2)+…+2+1 шагов, что можно представить как (N-1)N/2. Таким образом T(n) ≈ n2 для данного алгоритма.