Система обозначений в анализе алгоритмов

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

Пусть DА — множество конкретных проблем данной задачи, заданное в формальной системе. Пусть D?, DА — задание конкретной проблемы и |D|=N.

В общем случае существует собственное подмножество множества DА, включающее все конкретные проблемы, имеющие мощность N:

— обозначим это подмножество через DN:DN= {D?, DN : |D| = N};

— обозначим мощность множества DN через MDN> MDN=|DN |.

Тогда содержательно данный алгоритм, решая различные задачи размерности N, будет выполнять в каком-то случае наибольшее количество операций, а в каком-то случае наименьшее количество операций. Введем следующие обозначения:

1. F? ^(N) — худший случай — наибольшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

F? ^(N) = max {F? (D)}

DDN -худший случай на DN.

2. F? (N) — лучший случай — наименьшее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

Fa (N) = min {Fa (D)}

DDN — лучший случай на DN

3. ?(N) — средний случай — среднее количество операций, совершаемых алгоритмом А для решения конкретных проблем размерностью N:

a(N)=(1/MDN}·?{Fa(D)}

DIDN — средний случай на DN

3. Классификация алгоритмов по виду функции трудоёмкости

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

1. Количественно-зависимые по трудоемкости алгоритмы

Это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений:

Fa(D)=Fa(|D|)=Fa(N)

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

2.Параметрически-зависимые по трудоемкости алгоритмы

Это алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, для этой группы размерность входа обычно фиксирована), а конкретными значениями обрабатываемых слов памяти:

Fa(D) =Fa(d1,..,dn)=Fa(P1,..,Pm),m=

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

а) Вычисление xkпоследовательным умножением ? Fa(x,k) = Fa(k).

б) Вычисление ex=?(x-n/n!), с точностью до ? => Fa= Fa(х,?)

3. Количественно-параметрические по трудоемкости алгоритмы

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

Fa(D) =Fa(||D||,P1,..,Pm)=Fa(N,P1,..,Pm)

В качестве примера можно привести алгоритмы численных методов, в которых параметрически-зависимый внешний цикл по точности включает в себя количественно-зависимый фрагмент по размерности.

3.1 Порядково-зависимые по трудоемкости алгоритмы

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

Пусть множество D состоит из элементов (d1,…,dn), и ||D||=N,

Определим Dp= {(d1,…,dn)}-множество всех упорядоченных N-ок из d1 ,…,dn, отметим, что |Dp|=n!.

Если Fa(iDp)?Fa(jDp), где iDp, jDp, ?Dp, то алгоритм будем называть порядково-зависимым по трудоемкости.

Примерами таких алгоритмов могут служить ряд алгоритмов сортировки, алгоритмы поиска минимума и максимума в массиве. Рассмотрим более подробно алгоритм поиска максимума в массиве S, содержащим n элементов:

MaxS(S,n; Мах)

Max< S1

For i

If Max

Then Max

(количество выполненных операций присваивания зависит от порядка следования элементов массива)

Рандомно подобранные статьи с сайта:

Дональд Кнут. Глава 1. Основные понятия. 1.1 Алгоритмы. «Искусство программирования». (Часть 1)


Похожие статьи:

admin