Структуры данных и алгоритмы (1021739), страница 9
Текст из файла (страница 9)
ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ3.4.раторов без определения констант пропорциональности совпадает с наибольшимвременем выполнения оператора в данной последовательности.Время выполнения условных операторов состоит из времени выполнения условноисполняемых операторов и времени вычисления самого логического выражения.Время вычисления логического выражения обычно имеет порядок О(1).
Времядля всей конструкции if-then-else состоит из времени вычисления логическоговыражения и наибольшего из времени, необходимого для выполнения операторов, исполняемых при значении логического выражения true (истина) и призначении false (ложь).Время выполнения цикла является суммой времени всех исполняемых итерацийцикла, в свою очередь состоящих из времени выполнения операторов тела циклаи времени вычисления условия прекращения цикла (обычно последнее имеет порядок О(1)).
Часто время выполнения цикла вычисляется, пренебрегая определением констант пропорциональности, как произведение количества выполненныхитераций цикла на наибольшее возможное время выполнения операторов телацикла. Время выполнения каждого цикла, если в программе их несколько,должно определяться отдельно.Вызовы процедур) Для программ, содержащих несколько процедур (среди которых нет рекурсивных), можно подсчитать общее время выполнения программы путем последовательного нахождения времени выполнения процедур, начиная с той, которая не имеетвызовов других процедур. (Вызов процедур мы определяем по наличию оператораcall.) Так как мы предположили, что все процедуры нерекурсивные, то должна существовать хотя бы одна процедура, не имеющая вызовов других процедур.
Затемможно определить время выполнения процедур, вызывающих эту процедуру, используя уже вычисленное время выполнения вызываемой процедуры. Продолжая этотпроцесс, найдем время выполнения всех процедур и, наконец, время выполнениявсей программы.Если есть рекурсивные процедуры, то нельзя упорядочить все процедуры такимобразом, чтобы каждая процедура вызывала только процедуры, время выполнениякоторых подсчитано на предыдущем шаге.
В этом случае мы должны с каждой рекурсивной процедурой связать временную функцию Т(п), где п определяет объем аргументов процедуры. Затем мы должны получить рекуррентное соотношение дляТ(п), т.е. уравнение (или неравенство) для Т(п), где участвуют значения T(k) дляразличных значений k.Техника решения рекуррентных соотношений зависит от вида этих соотношений,некоторые приемы их решения будут показаны в главе 9. Сейчас же мы проанализируем простую рекурсивную программу.Пример 1.10.
В листинге 1.5 представлена программа вычисления факториала nl,т.е. вычисления произведения целых чисел от 1 до л включительно.Листинг 1.5. Рекурсивная программа вычисления факториалаfunction fact ( п: integer ) : integer;{ fact(n) вычисляет п! }begin(1)if n <= 1 then(2)fact:= 1else(3)fact:= n * fact(n - 1)end; { fact }Естественной мерой объема входных данных для функции fact является значение п.Обозначим через Т(п) время выполнения программы. Время выполнения для строк1.5. ВЫЧИСЛЕНИЕ ВРЕМЕНИ ВЫПОЛНЕНИЯ ПРОГРАММ35(1) и (2) имеет порядок О(1), а для строки (3) — О(1) + Т(п - 1). Таким образом, длянекоторых констант с и d имеем„) = (< + Г(га-1), е с л и Л > 1 ,Г([d,(11)если п < 1.Полагая, что га > 2, и раскрывая в соответствии с соотношением (1.1) выражениеТ(п - 1) (т.е.
подставляя в (1.1) п - 1 вместо п), получим Т(п) = 2с + Т(п - 2).Аналогично, если п > 3, раскрывая Т(га - 2), получим Т(п) = Зс + Т(п - 3).Продолжая этот процесс, в общем случае для некоторого i, п > i, имеемТ(га) = ic + Т(п - i). Положив в последнем выражении i = п - 1, окончательнополучаемТ(п) = с(п - 1) + Г(1) = с(п - 1) + d.(1.2)Из (1.2) следует, что Т(п) имеет порядок О(п).
Отметим, что в этом примереанализа программы мы предполагали, что операция перемножения двух целых чиселимеет порядок О(1). На практике, однако, программу, представленную в листинге1.5, нельзя использовать для вычисления факториала при больших значений п, таккак размер получаемых в процессе вычисления целых чисел может превышать длинумашинного слова. ПОбщий метод решения рекуррентных соотношений, подобных соотношению изпримера 1.10, состоит в последовательном раскрытии выражений T(k) в правой частиуравнения (путем подстановки в исходное соотношение k вместо п) до тех пор, покане получится формула, у которой в правой части отсутствует Т (как в формуле (1.2)).При этом часто приходится находить суммы различных последовательностей; еслизначения таких сумм нельзя вычислить точно, то для сумм находятся верхниеграницы, что позволяет, в свою очередь, получить верхние границы для Т(п).Программы с операторами безусловного переходаПри анализе времени выполнения программ мы неявно предполагали, что всеветвления в ходе выполнения процедур осуществлялись с помощью условных операторов и операторов циклов.
Мы останавливаемся на этом факте, так как определяливремя выполнения больших групп операторов путем применения правила сумм кэтом группам. Однако операторы безусловного перехода (такие как goto) могут порождать более сложную логическую групповую структуру. В принципе, операторы безусловного перехода можно исключить из программы. Но, к сожалению, язык Pascalне имеет операторов досрочного прекращения циклов, поэтому операторы переходапо необходимости часто используются в подобных ситуациях.Мы предлагаем следующий подход для работы с операторами безусловного перехода, выполняющих выход из циклов, который гарантирует отслеживание всегоцикла.
Поскольку досрочный выход из цикла скорее всего осуществляется после выполнения какого-нибудь логического условия, то мы можем предположить, что этоусловие никогда не выполняется. Но этот консервативный подход никогда не позволит уменьшить время выполнения программы, так как мы предполагаем полное выполнение цикла. Для программ, где досрочный выход из цикла не исключение, аправило, консервативный подход значительно переоценивает степень роста временивыполнения в наихудшем случае. Если же переход осуществляется к ранее выполненным операторам, то в этом случае вообще нельзя игнорировать оператор безусловного перехода, поскольку такой оператор создает петлю в выполнении программы, что приводит в нарастанию времени выполнения всей программы.Нам не хотелось бы, чтобы у читателя сложилось мнение о невозможности анализа времени выполнения программ, использующих операторы безусловного перехода,создающих петли.
Если программные петли имеют простую структуру, т.е. о любойпаре петель можно сказать, что они или не имеют общих элементов, или одна петлявложена в другую, то в этом случае можно применить методы анализа времени выполнения, описанные в данном разделе. (Конечно, бремя ответственности за пра36ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВвильное определение структуры петли ложится на того, кто проводит анализ.) Мыбез колебаний рекомендуем применять описанные методы для анализа программ, написанных на таких языках, как Fortran, где использование операторов безусловногоперехода является естественным делом, но для анализируемых программ допустимыпетли только простой структуры.Анализ программ на псевдоязыкеЕСЛИ мы знаем степень роста времени выполнения операторов, записанных с помощью неформального "человеческого" языка, то, следовательно, сможем проанализировать программу на псевдоязыке (такие программы будем называть псевдопрограммами).
Однако часто мы не можем в принципе знать время выполнения той части псевдопрограммы, которая еще не полностью реализована в формальныхоператорах языка программирования. Например, если в псевдопрограмме имеетсянеформальная часть, оперирующая абстрактными типами данных, то общее времявыполнение программы в значительной степени зависит от способа реализации АТД.Это не является недостатком псевдопрограмм, так как одной из причин написанияпрограмм в терминах АТД является возможность выбора реализации АТД, в томчисле по критерию времени выполнения.При анализе псевдопрограмм, содержащих операторы языка программирования ивызовы процедур, имеющих неформализованные фрагменты (такие как операторыдля работы с АТД), можно рассматривать общее время выполнения программы какфункцию пока не определенного времени выполнения таких процедур.
Время выполнения этих процедур можно параметризовать с помощью "размера" их аргументов. Так же, как и "размер входных данных", "размер" аргументов — это предметдля обсуждения и дискуссий. Часто выбранная математическая модель АТД подсказывает логически обоснованный размер аргументов. Например, если АТД строится наоснове множеств, то часто количество элементов множества можно принять за параметр функции времени выполнения. В последующих главах вы встретите многопримеров анализа времени выполнения псевдопрограмм.1.6.
Практика программированияПриведем несколько рекомендаций и соображений, которые вытекают из нашегопрактического опыта построения алгоритмов и реализации их в виде программ. Некоторые из этих рекомендаций могут показаться очевидными или даже банальными,но их полезность можно оценить только при решении реальных задач, а не исходя изтеоретических предпосылок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
