Главная Промышленная автоматика.

(1) и (2) имеет порядок 0(1), а для строки (3) - 0(1) + Т(п - 1). Таким образом, для некоторых констант с и d имеем

с + Т(п - 1), если п > 1,

Т(п) =

(1.1)

"d, если и < 1.

Полатая, что та > 2, и раскрывая в соответствии с соотношением (1.1) выражение Т{п- 1) (т.е. подставляя в (1.1) и - 1 вместо и), получим Т(п)= 2с + Т(п - 2). Аналотично, если п > 3, раскрывая Т{п - 2), получим Т(п)= Зс + Т(п - 3). Продолжая этот процесс, в общем случае для некоторого г, п > г, имеем Т(п) = гс + Т(п - г). Положив в последнем выражении г = п - 1, окончательно получаем

T(n) = c(n-l)+T(l) = c(nl)+d. (1.2)

Из (1.2) следует, что Т(п) имеет порядок 0{п). Отметим, что в этом примере анализа программы мы предполагали, что операция перемножения двух целых чисел имеет порядок 0(1). На практике, однако, программу, представленную в листинге 1.5, нельзя использовать для вычисления факториала при больших значений и, так как размер получаемых в процессе вычисления целых чисел может превышать длину машинного слова. П

Общий метод решения рекуррентных соотношений, подобных соотношению из примера 1.10, состоит в последовательном раскрытии выражений Т{К)ъ правой части уравнения (путем подстановки в исходное соотношение k вместо п) до тех пор, пока не получится формула, у которой в правой части отсутствует Т (как в формуле (1.2)). При этом часто приходится находить суммы различных последовательностей; если значения таких сумм нельзя вычислить точно, то для сумм находятся верхние границы, что позволяет, в свою очередь, получить верхние границы для Т(п).

Программы с операторами безусловного перехода

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

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

Нам не хотелось бы, чтобы у читателя сложилось мнение о невозможности анализа времени выполнения программ, использующих операторы безусловного перехода, создающих петли. Если программные петли имеют простую структуру, т.е. о любой паре петель можно сказать, что они или не имеют общих элементов, или одна петля вложена в другую, то в этом случае можно применить методы анализа времени выполнения, описанные в данном разделе. (Конечно, бремя ответственности за пра-



вильное определение структуры петли ложится на того, кто проводит анализ.) Мы без колебаний рекомендуем применять описанные методы для анализа программ, написанных на таких языках, как Fortran, где использование операторов безусловного перехода является естественным делом, но для анализируемых программ допустимы петли только простой структуры.

Анализ программ на псевдоязыке

ЕСЛИ мы знаем степень роста времени выполнения операторов, записанных с помощью неформального "человеческого" языка, то, следовательно, сможем проанализировать программу на псевдоязыке (такие программы будем называть псевдопрограммами). Однако часто мы не можем в принципе знать время выполнения той части псевдопрограммы, которая еще не полностью реализована в формальных операторах языка программирования. Например, если в псевдопрограмме имеется неформальная часть, оперирующая абстрактными типами данных, то общее время выполнение программы в значительной степени зависит от способа реализации АТД. Это не является недостатком псевдопрограмм, так как одной из причин написания программ в терминах АТД является возможность выбора реализации АТД, в том числе по критерию времени выполнения.

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

1.6. Практика программирования

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

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

2. Применяйте инкапсуляцию. Все процедуры, реализующие АТД, поместите в одно место программного листинга. В дальнейщем, если возникнет необходимость изменить реализацию АТД, можно будет корректно и без особых затрат внести какие-либо изменения, так как все необходимые процедуры локализованы в одном месте программы.

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



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

4. Станьте "кузнецом" инструментов. На языке программистов инструмент (tool) - это программа с широким спектром применения. При создании программы подумайте, нельзя ли ее каким-либо образом обобщить, т.е. сделать более универсальной (конечно, с минимальными программистскими усилиями). Например, предположим, что вам необходимо написать программу, составляющую расписание экзаменов. Вместо заказанной программы можно написать программу-инструмент, раскрашивающий вершины обычного графа (по возможности минимальным количеством цветов) таким образом, чтобы любые две вершины, соединенные ребром, были закрашены в разные цвета. В контексте расписания экзаменов вершины графа - это классы, цвета - время проведения экзаменов, а ребра, соединяющие две вершины-класса, обозначают, что в этих классах экзамены принимает одна и та же экзаменационная комиссия. Такая программа раскраски графа вместе с подпрограммой перевода списка классов в множество верщин графа и цветов в заданные временные интервалы проведения экзаменов составит расписание экзаменов. Программу раскраски можно использовать для решения задач, совсем не связанных с составлением расписаний, например для задания режимов работы светофоров на сложном перекрестке, как было показано в разделе 1.1.

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

Пример 1.11. В качестве примера рассмотрим программу spell, написанную Джонсоном (S.C. Johnson) с использованием команд UNIX . На вход этой программы поступает файл /1, состоящий из текста на английском языке, на выходе получаем все слова из /i, не совпадающие со словами из небольшого словаря. Эта программа воспринимает имена и правильно написанные слова, которых нет в словаре, как орфографические ошибки. Но обычно выходной список ошибок достаточно короткий, поэтому его можно быстро пробежать глазами и определить, какие слова в нем не являются ошибками.

Первый фильтр, используемый программой spell, - это команда translate, которая имеет соответствующие параметры и заменяет прописные буквы на строчные, пробелы - на начало новых строк, а остальные символы оставляет без изменений. На выходе этой команды мы получаем файл /2, состоящий из тех же СЛ()В, что и файл /1, но каждое слово расположено в отдельной строке. Далее выполняется команда sort, упорядочивающая строки входного файла в алфавитном порядке. Результатом выполнения этой команды является файл /3, содержащий отсортированный список (возможно, с повторениями) слов из файла /2. Затем команда unique удаляет

Мы могли бы использовать полный словарь, но многие орфографические ошибки совпа-

UNIX - торговая марка Bell Laboratories. Мы могли бы использовать полный слов; дают со словами, которые почти никогда не применяются.





0 1 2 3 4 5 6 7 [8] 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.002