Выполняя простые операции сложения, получаем, что общее время выполнения программы равно

(7 + 5Л + 6В + 7С +-2D + E + 3F + 4G + 8H + 6J

+ ЗК+ 4L + 3P + iQ + 6R + 2S)u (7)

плюс время, затрачиваемое на ввод и вывод. Чтобы понять смысл формулы (7), нужно рассмотреть пятнадцать неизвестных А, В, С, D, Е, F, G, Н, J, К, L, Р, Q, R, S и связать их с соответствующими характеристиками входных данных. Проиллюстрируем общие принципы решения проблем подобного рода.

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

He все уравнения, полученные с помощью закона Кирхгофа, будут линейно независимыми, например в данном случае мы видим, что первое и второе уравнения явно эквивалентны. Более того, последнее уравнение можно вывести из остальных, так как из третьего, четвертого и пятого следует, что Н = R. Таким образом, шестое означает, что К = L - R. Во всяком случае мы уже исключили шесть из пятнадцати неизвестных:

Л = С, ER + l, F = R + G, H = R, K = L-R, Q = P - R. (8)

Первый закон Кирхгофа - это очень эффективное средство; более подробно мы рассмотрим его в разделе 2.3.4.1.

Следующий шаг состоит в том, чтобы попытаться сопоставить переменные с важными характеристиками данных. Из строк 24, 25, 30 и 36 находим, что

В + С = количество слов ввода = 16Х - 1, (9)

где X - число перфокарт с входной информацией. Из строки 28 получгьем, что

В = количество "(" во вводе = количество циклов во вводе. (10)

Аналогично из строки 34 получаем

D = количество ")" во вводе = количество циклов во вводе. (И)

А теперь из (10) и (11) получаем то, что нельзя вывести из закона Кирхгофа:

B = D. (12)

Из строки 64 получаем

Н = количество циклов в выводе (включая единичные циклы). (13)

Из строки 82 следует, что R равно этой же величине; в данном случае соотношение Н - R можно было вывести из закона Кирхгофа, так как оно уже содержится в (8).

Учитывая тот факт, что каждое непустое слово в конце концов помечается, из строк 29, 35 и 67 находим, что

J = Г - 2В, (14)

где Y - число непустых слов, содержащихся в перестановках ввода. Учитывая то, что каждый отличный от других элемент, содержащийся во входной перестановке, записывается в вывод только один раз, либо в строке 65, либо в строке 72, получаем

Р - Н + Q = количество различных элементов во вводе. (15)

(См. соотношения (8).) Если немного поразмыслить, это очевидным образом сле-д>ет также из строки 80. И, наконец, из строки 85 видно, что

S = количество единичных циклов в выводе. (16)

Очевидно, что величины В, С, Н, J, Р и 5, которые мы сейчас интерпретировали как независимые параметры, влияют на время выполнения программы А.

Теперь остается проанализировать только неизвестные G и L. Для этого придется проявить немного больше изобретательности. Просмотры входной информации, которые начинаются в строках 41 и 74, всегда заканчиваются либо в строке 47 (прошлый раз), либо в строке 80. В течение каждого из этих Р +1 циклов команда "INC3 1" вьшолняется В + С раз. Это имеет место только в строках 44, 68 и 77, поэтому получаем нетривиальное соотношение

G + J + L=iB + C){P + l), (17)

связывающее неизвестные G и L. К счастью, время выполнения (7)-это функция от G -I- L (так как оно включает слагаемые -h 3F -ь 46* -h ЗЯ -ь 4L н- = -h 7G -ь • • • + 7L + ), поэтому нам не нужно больше пытаться анализировать величины G и L по отдельности.

Просуммировав все эти результаты, находим, что общее время выполнения программы без учета времени, затрачиваемого на операции ввода-вывода, равно

(112iVA + 304Х - 2М -У + 11U + 2V - П)и. (18)

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

Л" - количество перфокарт ввода;

Y - количество непустых полей во вводе (исключая конечное "="); М - количество циклов во вводе;

Л - количество имен различных элементов во вводе;

и - количество циклов в выводе (включая единичные циклы);

V - количество единичных циклов в выводе.

Таблица 2

ПЕРЕМНбЖЕНИЕ ПЕРЕСТАНОВОК ЗА ОДИН ПРОХОД

{ аЧ/ д ) { b с d ) { а е d ) ( f а d е ) { b д f а е ) а -¥ ddaaaaaaaaaaaddddddeeeeeeeeaa b -> ccccccccggggggggggggggggbbbbb с-¥eeeddddddcccccccccccccccccccc dggggggg)))dd)))bbbbbddddddddd ebbbbbbbbbbbbbbaaa))))bb)))))e f -ffffeeeeeeeeeeeeeeaaaaaaaafff

ga))))ffffffffffffffffffffgggg

Следовательно, можно сделать вывод, что анализ такой программы, как А, во многих отношениях подобен решению занимательной головоломки.

Ниже мы покажем,что если на выходе предполагается получить случайную перестановку, то средние величин U и V будут равны Hjy и 1 соответственно.

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

Но не менее часто приходится иметь дело с новыми методами, которые идеально подходят для компьютера, но совершенно непригодны для человека. Главная причина этого состоит в том, что компьютер "думает" по-другому; тип его памяти, с помощью которой он запоминает информацию, отличается от типа памяти человека. Это различие можно проследить на примере нашей задачи перемножения перестановок. Используя приведенный ниже алгоритм, компьютер может вьшолнить умножение перестановок "одним махом", запоминая текущее состояние перестановки в целом по мере перемножения циклов. Предназначенный для человека алгоритм А просматривает формулу много раз, по одному для каждого элемента вывода, в то время как новый алгоритм делает все за один проход. Homo sapiens на такое вряд ли способен.

Что представляет собой предназначенный для компьютера метод перемножения перестановок? Главная идея проиллюстрирована в табл. 2. В столбце, расположенном в этой таблице под каждым символом выражения, которое представлено в виде циклов, показано, какая перестановка выражена частичными циклами справа. Например, фрагмент формулы "... d e){b д f а е)" представляет перестановку

abcdef дЛ ? а f)

е д с b ?

которая появляется в таблице под крайним справа символом d.

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