Математический анализ нерекурсивных алгоритмов

Общий план анализа эффективности нерекурсивных алгоритмов

1. Выберите параметр (или параметры), по которому будет оцениваться размер входных данных алгоритма.

2. Определите основную операцию алгоритма. (Как правило, она находится в наиболее глубоко вложенном внутреннем цикле алгоритма.)

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

4. Запишите сумму, выражающую количество выполняемых основных операций алгоритма.

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

Формулы, использующиеся при анализе алгоритмов:

Пример 1. Рассмотрим задачу поиска наибольшего элемента в списке из n чисел. Для простоты предположим, что этот список реализован в виде массива. Ниже приведен псевдокод алгоритм решения этой задачи.

Размер входных данных будем оценивать по количеству элементов в массиве, т.е. числом n. Операции, выполняемые чаще всего, находятся во внутреннем цикле for алгоритма. Таких операций две: сравнение и присваивание Поскольку сравнение выполняется на каждом шаге цикла, а присваивание — нет, будем считать, что основной операцией алгоритма является операция присваивания. (Т.к. для любого массива размером n количество операций сравнения в рассматриваемом алгоритме постоянно. Поэтому нет смысла отдельно рассматривать эффективность алгоритма для худшего, среднего и лучшего случаев.) Обозначим через С (n) количество выполняемых в алгоритме операций сравнения. Известно, что за один цикл в алгоритме выполняется одна операция сравнения. Этот процесс повторяется для каждого значения переменной цикла i, которое изменяется от 1 до n-1 включительно. Поэтому для С (n) получаем следующую сумму:

Пример 2. Рассмотрим задачу проверки единственности элементов. Другими словами, нужно убедиться, что все элементы массива различны. Эту задачу можно решить с помощью приведенного ниже несложного алгоритма.

В этом алгоритме размер входных данных будем оценивать по количеству элементов в массиве, т.е. числом n. Поскольку в во внутреннем цикле алгоритма выполнятся только одна операция сравнения двух элементов, ее и будем считать основной. Количество операций сравнения будет зависеть не только от общего числа n элементов в массиве, но и от того, есть ли в массиве одинаковые элементы, и если есть, то на каких позициях они расположены. Рассмотрим наихудший случай. После анализа внутреннего цикла алгоритма приходим к выводу, что наихудший случай входных данных (т.е. когда цикл выполняется от начала до конца, а не завершается досрочно) может возникнуть при обработке массивов двух типов: а) в которых нет одинаковых элементов; б) в которых два одинаковых элемента находятся рядом и расположены в самом конце массива. В этих случаях, при каждом повторе внутреннего цикла выполняется одна операция сравнения. При этом j последовательно принимает значения от i + 1 до n-1. Внутренний цикл каждый раз повторяется при каждом выполнении внешнего цикла. При этом переменная внешнего цикла i последовательно принимает значения от 0 до n-2. Таким образом, получаем:

Пример 3. Для двух заданных матриц А и В размером nхn определите временную эффективность алгоритма их умножения С = АВ. По определению С — это матрица размером nхn, элементы которой являются скалярными произведениями соответствующих строки матрицы А и столбца матрицы В.

В этом алгоритме размер входных данных соответствует размеру матрицы n. Во внутреннем цикле алгоритма выполняются две арифметические операции: умножение и сложение. В качестве основной операции алгоритма можно выбрать любую. Мы рассмотрим случай, когда в качестве основной выбрана операция умножения. Составим сумму для общего числа операций умножения М (n), выполняемых в алгоритме. Поскольку это число зависит только от размера исходных матриц, не требуется отдельно рассматривать наихудший, типичный и наилучший случаи. На каждом шаге внутреннего цикла алгоритма выполняется только одна операция умножения. При этом значение переменной цикла к последовательно изменяется от нижней границы 0 до верхней границы n-1. Поэтому количество операций умножения, выполняемых для каждой пары значений переменных i и j, можно записать как Соответственно, общее количество операций умножения М (n) выражается следующей тройной суммой:

Время выполнения алгоритма на конкретном компьютере можно оценить с

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

Пример 4. С помощью приведенного ниже алгоритма можно определить количество разрядов, которое будет иметь положительное десятичное число в двоичном представлении.

В этом алгоритме операция сравнения n > 1, которая выполняется чаще всего, не находится в его внутреннем цикле while. Однако она определяет, будет ли выполняться все тело цикла. Поскольку количество выполняемых операций сравнения всегда на единицу больше, чем общее число повторов выполнения цикла, выбор основной операции алгоритма не имеет большого значения. Более важно в этом примере то, что в процессе вычислений переменная цикла принимает всего насколько значений в интервале от ее минимального до максимального значения. Поэтому для определения количества раз, которые будет выполняться цикл, мы должны использовать другой метод. Поскольку на каждом шаге цикла значение переменной n уменьшается приблизительно вдвое, то искомый результат должен примерно равняться log₂n. На самом деле точная формула для определения количества выполняемых операций сравнения n> 1 равна [log₂n] + 1.

Дата добавления: 2014-01-20