Объем программы

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

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

Решение этой проблемы связано с тем, что можно определить абсолютный минимум длины представления самого длинного оператора или имени операнда. Минимальная длина зависит только от числа элементов в словаре h. В общем случае log₂ h есть минимальная длина (в битах) всей программы. Под битом здесь понимается логическая единица информации – символ, оператор, операнд – то, чем оперирует программист при создании программы.

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

V = N log₂ h (2.2)

где N = N₁ + N₂ -длина реализации; а h = h₁ + h₂ - ее словарь.

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

Потенциальный объем V^*

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

Обозначив соответствующие программные параметры возможно кратчайшей или наиболее сжатой формы алгоритма звездочками, из уравнения (2.1) получим, что минимальный (или потенциальный) объем равен

V^* = (N₁^* + N₂^*) log₂(h₁^* ₊ h₂^*) (2.3)

Но в минимальной форме ни операторы, ни операнды не требуют повторений, поэтому

N₁^* = h₁^*; N₂^* = h₂^*

что дает нам

V^* = (h₁^* ₊ h₂^*) log₂(h₁^* ₊ h₂^*)

Кроме того, известно минимально возможное число операторов h₁^* для любого алгоритма. Каждый алгоритм должен включать один оператор для имени функции или процедуры и один в качестве символа присваивания или группировки, т.е. минимальное значение h₁^*=2.

Уравнение теперь примет вид:

V^* = (2₊ h₂^*) log₂(2₊ h₂^*), (2.4)

где h₂^* должно представлять собой число различных входных и выходных параметров.

Из уравнения (3.4) следует, что потенциальный объем V^* любого алгоритма не должен зависеть от языка, на котором он может быть выражен. Если h₂^* расценивается как число единых по смыслу (неизбыточных) операндов, то V^* оказывается наиболее полезной мерой содержания алгоритма.

Вернемся к примеру программы для алгоритма Евклида и определим его объем для программ на Паскале.

V =N * log₂ h = 61* log₂ 18 = 254.4 бита.

Чтобы найти потенциальный объем, нам нужно подсчитать число требуемых входных и выходных параметров. В данном случае это А, В и GCD, так что h₂^*=3. Следовательно, потенциальный объем:

V^* = (2 +h₂^*) log₂(2 + h₂^*) = (2+3) log₂(2+3) = 11,6 бита

Как уже упоминалось выше, при переводе алгоритма с одного языка на другой его потенциальный объем V^* не меняется, но действительный объем V увеличивается или уменьшается в зависимости от развитости рассматриваемых языков. Однако легко заметить, что не может быть гладкого перехода от выражения на потенциальном языке, для которого V = V^*, к любому менее развитому языку, для которого V > V^*. Такой резкий переход обусловлен тем, что для потенциального языка N^*= h^*, в то время как для всех других языков применяется уравнение длины и N > h.

Пример определение времени выполнения программы:

Дата добавления: 2014-11-16