Подсчет числа простейших операций

В соответствии с методом подсчета простейших операций алгоритм представляется в виде программы на развитом языке программирования (например, Pascal). Определяется множество простейших операций высокого уровня, которые не зависят от языка программирования. К таким операциям относятся:

1) присваивание переменной значения,

2) вызов метода (процедуры или функции),

3) выполнение арифметической операции,

4) сравнение двух значений,

5) индексация массива,

6) переход по ссылке на объект,

7) возвращение из метода.

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

Рассмотрим процесс подсчета простейших операций на примере алгоритма определения максимального значения в одномерном массиве X, состоящего из N элементов. На рисунке 3.2 приводится код данного алгоритма на языке Pascal.

Begin

currentMax:= X[0];

for i:= 1 to N-1 do

if currentMax < X[i] then currentMax:= X[i];

end;

Рисунок 3.2 – Pascal-код алгоритма определения максимального значения в массиве

Приведем рассуждения, формулируемые в процессе анализа:

- на этапе инициализации переменной currentMax и присваивания ее значения X[0] выполняются две простейшие операции (индексация массива и присваивание значения); таким образом, счетчик операций равен 2;

- в начале цикла for счетчик i получает значение 1, что соответствует одной простейшей операции присваивания;

- перед выполнением тела цикла проверяется условие i< N (операция сравнения); такое сравнение выполняется N раз, поэтому счетчик простейших операций увеличивается еще на N единиц;

- тело цикла выполняется для значений i, равных 1, 2, …, N-1. При каждой итерации X[i] сравнивается с currentMax (две простейших операции – индексирование и сравнение), значение X[currentMax], возможно, присваивается переменной currentMax (две операции – сложение и присваивание), а счетчик i увеличивается на 1 (две операции – сложение и присваивание). Следовательно, при каждой итерации цикла выполняется 4 или 6 простейших операций, в зависимости от выполнения одного из условий X[i]£ currentMax или X[i]> currentMax. Таким образом, при выполнении тела цикла в счетчик операций добавляется 4(N–1) или 6(N–1);

- при возвращении значения переменной currentMax однократно выполняется одна простейшая операция.

Итак, число простейших операций К(N), выполняемых алгоритмом, минимально равно

,

а максимально

.

Число выполняемых простейших операций равно минимально (К(N) = 5N) в том случае, если X[0] является максимальным элементом массива, т. е. переменной currentMax не присваивается нового значения. Число выполняемых операций максимально равно 7N–2 в том случае, если элементы массива упорядочены по возрастанию, и переменной currentMax присваивается значение при каждой итерации цикла.