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

Типы алгоритмов. Сложность алгоритмов.

Алгоритмы

Под алгоритмом понимается описание последовательностидействий,необходимых для решения задачи (алгоритм не содержит описания данных и их структур, а описывает только действия).

Существует несколько форм описания алгоритмов:

1. словесное (для решения неформализованных задач)

2. запись с использованием математической либо другой специальной нотации

3. графическое изображение алгоритма

4. запись на метаязыке

5. запись на алгоритмическом языке

Название алгоритма может указывать либо на его назначение, либо на метод решения задачи.

Существует 2 типа алгоритмов: детерминированные и недетерминированные.

Детерминированные алгоритмыпредполагают прямое решение задачи без использования повторов и выбора вариантов. Такой алгоритм не содержит элементов неопределённости. (Они всегда простые.)

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

Для такого алгоритма невозможно даже сказать наперёд,будет ли получено решение при данном наборе входных данных.

Некоторые задачи могут быть решены с использованием обоих типов алгоритмов. Например, задача нахождения нужной строки в таблице. Если индекс строки известен, то алгоритм обращения к этой строке является детерминированным. Если индекс строки неизвестен заранее, то для нахождения строки может быть применён алгоритм случайного поиска (недетерминированный) (строка ищется по какому-то признаку и строки перебираются случайным образом). Такой способ эффективен для больших таблиц. Также может использоваться последовательный поиск перебором (II-й недетерминированный алгоритм). При таком методе строка будет найдена за 2n итераций (n-число строк). Последовательный поиск эффективен для малых объёмов.

Сложность алгоритма определяет зависимость времени работы алгоритма от объёма обрабатываемых данных.

Основные типы сложности алгоритмов:

1.Постоянная сложность – имеют алгоритмы, рассчитанные на обработку фиксированного объёма данных.

2.Линейная сложность (например, алгоритм обработки массива в памяти). Время работы такого алгоритма может быть оценено так: an+b, где n – количество элементов массива, a – время, необходимое для выполнения операций над отдельным элементом массива, b – время, затрачиваемое на выполнение вспомогательных операций.

3.Квадратичная сложность (например, алгоритм пузырьковой сортировки). (n-1) сравнений для определения I-го элемента,(n-2) – II-го элемента, (n-1)+(n-2)+…+3+2+1=. Для больших n время работы алгоритма ~.

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

Пример оценки сложности по тексту программы (алгоритм сортировки) :

Procedure сортировка;

For k:=1 to n-1 do

Min:=A(k); lok:=k;

For i:=k+1 to n do

If min>A(i) then

Min:=A(i); loc:=I;

A(loc):=A(k); A(k):=min

End;

В данной прог-е внешний цикл исполняется n-1 раз, а внутренний исполняется в среднем раз.Общее число исполнений внутреннего цикла = . Для больших n количество исполнений ~. Т.е. алгоритм обладает квадратичной сложностью.

Оценка сложности алгоритма умножения 2-х матриц размерности n*n:

For i:=1 to n do

For j:=1 to n do

C(i,j):=0;

For k:=1 to n do

C(i,j):=C(i,j)+A(i,k)*B(k,j);

Сложность ~ (т.к. 3 цикла).

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

Можно дать формальное определение сложности алгоритма, используя нотацию «большого О» и понятие порядка функции. Считается, что 2 ф-ции f(n) и g(n) одного порядка, если для больших n существует константа k: . И формально такое высказывание записывается так: f(n)=O(g(n)).

Сложность алгоритмов обозначается:

O(n) – для алгоритмов линейного поиска

O() - для пузырьковой сортировки

O() - для перемножения матриц

O() - для двоичного поиска