3.Реализация оценки эффективности алгоритмов в программе

3.1.Исходные данные

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

• Входные данные в большей или полной ее части соответствут ожидаемым выходным данным (например, почти или полностью упорядоченные исходные массивы для задачи сортировки).

• Входные данные неизвестны (например, исходные массивы заполнены случайными значениями).

• Входные данные, относительно ожидаемых выходных данных представляют наихудший случай их представления (например, исходные массивы упорядочены в обратном порядке для задачи сортировки).

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

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

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

3.2.Способы оценки эффективности

Для оценки эффективности выполнения алгоритмов сортировки в программе реализованы одновременно два способа:

1. Подсчет условной эффективности по формуле Eff=Comp+Chang*10, где Comp – кол-во сравнений, Chang – кол-во присваиваний, задействованных в ходе выполнения алгоритма..

2. Замер времени выполнения алгоритма при многочисленных его повторениях (кол-во повторений задается пользователем, по умолчанию равно 1000000).

Эффективность определяется по принципу – чем меньше задействовано операций (или затрачено времени), тем лучше.

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

Для оценки эффективности выполнения алгоритмов поиска условно примем кол-во операций сравнений и общее кол-во итераций в цикле.

3.3.Реализация подсчета кол-ва сравнений, присваиваний и эффективности в программе

Для подсчета кол-ва присваиваний и сравнений перед или после соответствующих действий в алгоритме увеличиваются соответствующие счетчики. Например, такой простой код …

for(i=0; i<size; i++)

a++;

будет дополнен следующими строчками кода для подсчета эффективности:

Changes++; // увеличиваем счетчик присваиваний перед предстоящим

// присваиванием начального значения для счетчика в цикле ниже

Compares++; // увеличиваем счетчик сравнений перед предстоящим

// сравнением для условия выхода из цикла (i<size)

for (i=0; i<size; i++) {

Changes++; // увеличиваем счетчик присваиваний перед предстоящим

// присваиванием (a++)

a++;

Changes++; // увеличиваем счетчик присваиваний перед предстоящим

// присваиванием счетчика цикла (i++)

Compares++; // увеличиваем счетчик сравнений перед предстоящим

// сравнением для условия выхода из цикла (i<size)

}

Eff=Compares+Changes*10; // считаем эффективность по формуле

Таким образом, после выполнения данного фрагмента, в программе будут доступны данные об эффективности выполнения этого фрагмента. Аналогичный подход был применен при создании алгоритмов сортировки в программе.