Измеримые свойства алгоритмов
Если задана реализация алгоритма на некотором языке можно идентифицировать все операнды, определенные как переменные или константы, используемые в этой реализации. Аналогично можно идентифицировать все операторы, определенные как символы или комбинации символов, влияющие на значение или на порядок операндов. Исходя из идентификации операторов и операндов, можно определить ряд измеримых категорий, обязательно присутствующих в любой версии любого алгоритма. Они определяются метриками, с помощью которых могут быть получены основные характеристики качества программ.В состав измеримых свойств любого представления алгоритма (или программы) могут быть включены следующие метрические характеристики:- h1 - число простых (уникальных) операторов, появляющихся в данной реализации;
- h2 - число простых (уникальных) операндов, появляющихся в данной реализации;
- N1 - общее число всех операторов, появляющихся в данной реализации;
- N2 - общее число всех операндов, появляющихся в данной реализации;
- f1j - число вхождений j-го оператора, где j = 1,2,3 ... h1;
- f2j - число вхождений j-го операнда, где j = 1,2,3 ... h2.
Отправляясь от этих основных метрических характеристик для программы, удобно определить:
словарь h h = h1 + h2
и длину N N = N1 + N2
реализации программы.
В соответствии с данными определениями должны выполняться следующие три соотношенияРассмотрим пример вычисления введенных метрик для программы, реализующей широко известный алгоритм Евклида нахождения наибольшего общего делителя (НОД) двух целых чисел. Возможные варианты программы на языках Паскаль приведены в таблице.
Программа на Паскале |
Function GCD (a,b: integer): integer; Label L1, L2; Var G, R : integer; Begin If (a=0) then L1: begin GCD := b; return end; If (b=0) then Begin GCD := a; return end; L2: G := a/b; R := a - b*G; If (R=0) GOTO L1; a :=b; b:=R; GOTO L2; End. |
Результаты подсчета числа типов операторов и операндов и их общего количества сведены в таблицу. При подсчете использовались следующие соображения.
В отношении классификации операторов интуитивно ясно, что символы :
:=- знак присваивания;
=- знак равенства (или знак присваивания в программе на Си);
--- знак вычитания;
/ -знак деления;
* - знак умножения
соответствуют их обычному определению.
Оператор | I | F1i | Операнд | J | F2j |
; | GCD | ||||
:= | G | ||||
= | R | ||||
() или begin end | A | ||||
If | B | ||||
/ | |||||
* | |||||
- | |||||
GOTO L1 | |||||
GOTO L2 | |||||
Function GCD | |||||
Return |
Соответственно, измеримые метрики программы на Паскале будут равны
η1 = 12; N1 = 40; η2 = 6; N2 = 21; η = 18; N = N1 + N2 = 61; 58,53