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

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

1. Время выполнения операторов присваивания, чтения и записи обычно имеет порядок О (1). Есть несколько исключений из этого правила, например в языках Pascal, C и других, где можно оперировать с массивами как с переменными, или в любых других языках, допускающих вызовы функций в операторах присваивания.

2. Время выполнения последовательности операторов определяется с помощью правила сумм. Поэтому степень роста времени выполнения последовательности oпeраторов без определения констант пропорциональности совпадает с наибольшим временем выполнения оператора в данной последовательности.

3. Время выполнения условных операторов состоит из времени выполнения условно исполняемых операторов и времени вычисления самого логического выражения. Время вычисления логического выражения обычно имеет порядок О (1). Время для всей конструкции if-then-else состоит из времени вычисления логического выражения и наибольшего из времени, необходимого для выполнения операторов, исполняемых при значении логического выражения true (истина) и при значении false (ложь).

4. Время выполнения цикла является суммой времени всех исполняемых итераций цикла, в свою очередь состоящих из времени выполнения операторов тела цикла и времени вычисления условия прекращения цикла (обычно последнее имеет порядок О (1)). Часто время выполнения цикла вычисляется, пренебрегая определением констант пропорциональности, как произведение количества выполненных итераций цикла на наибольшее возможное время выполнения операторов тела цикла. Время выполнения каждого цикла, если в программе их несколько, должно определяться отдельно.

5. Вызовы подпрограмм (процедур). Для программ, содержащих несколько процедур (среди которых нет рекурсив­ных), можно подсчитать общее время выполнения программы путем последовательного нахождения времени выполнения процедур, начиная с той, которая не имеет вызовов других процедур. Так как мы предположили, что все процедуры нерекурсивные, то должна существовать хотя бы одна процедура, не имеющая вызовов других процедур. Затем можно определить время выполнения процедур, вызывающих эту процедуру, используя уже вычисленное время выполнения вызываемой процедуры. Продолжая этот процесс, найдем время выполнения всех процедур и, наконец, время выполнения всей программы.

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

Техника решения рекуррентных соотношений зависит от вида этих соотношений. Существуют три различных подхода к их решению. Детальное их рассмотрение можно найти в работе [60].

1. Нахождение функции , которая мажорировала бы для всех значений (т.е. для всех должно выполняться неравенство ). Иногда сначала определяют только вид функции , предполагая, что она зависит от некоторых пока неопределенных параметров (например, , где ‑ неопределенный параметр), затем подбираются такие значения параметров, чтобы для всех значений выполнялось неравенство .

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

3. Третий подход заключается в использовании производящих функций

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