2.Методы оценки алгоритмов

2.1.Основные понятия

Критериями оценки того или иного алгоритма обычно выбираются его сложность и трудоемкость.

Сложность – это качество, оцениваемое объемом памяти, необходимым для реализации алгоритма. Измеряется в байтах. Не следует путать это понятие со сложностью структуры алгоритма (там основное - количество связей).

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

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

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

Оценками этой случайной величины могут служить:

`q - среднее значение трудоемкости, а также q_min и q_max – минимальные и максимальные значения трудоемкости.

Величина `q полезна тогда, когда речь идет о массовом (многократном) применении алгоритма. Если, например, алгоритм реализуется большое число раз (N), то величина N может служить хорошей оценкой общего объема работ по применению алгоритма.

Однако, если речь идет о малом или даже однократном применении алгоритма, более пригодны оценки q_min и q_max. .

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

Рассмотрим пример БСА:

Θ_i

Рассмотрим, как с помощью этой модели можно оценить интересующие нас характеристики. Начнем с оценки q =`q.

В общем случае блок-схему алгоритма можно представить в виде графа G с (К+2)-мя вершинами, где О и К соответствуют началу и концу алгоритма, а остальные К вершин – блокам схемы.

Каждая вершина i характеризуются трудоемкостью q_i ее выполнения. Переходы между блоками i и j обозначены в модели дугами (i,j). Дуга характеризуется вероятностью перехода P_ij в процессе реализации алгоритма. Будем считать P_ij постоянными и известными, также как и q_i, i=1,..,k Естественно, выполняются условия:

k

Σ P_ij=1 , i=1,…,k

i=1

Предположим, что нам каким-то образом удалось определить числа n_i – среднее число прохождения блока i в процессе реализации алгоритма.

Тогда величину q_i легко оценить значением:

k

`q = åq_i*n_i (1)

i=1

Оценка вероятностей P_ij - отдельная проблема, мы не будем ее касаться.

Приведем лишь примеры оценки в простейших случаях.

Пусть цикл задается блоком модификации, например таким:

Второй простейший пример- разветвление:

Такое представление справедливо, если полагать, что случайная величина A распределена на отрезке [a,b] равномерно.

Методы оценки трудоемкости алгоритмов, в общем случае, разнятся способом вычисления среднего значения числа прохождения i-го блока (n_i).

Предлагаю ознакомиться с аналогичными статьями: