Д. Кнут - Искусство программирования том 1 (1119450), страница 46
Текст из файла (страница 46)
Учитывая то, что каждый огпличнмй ощ других элемент, содержащийся во входной перестановке, записывается в вывод только один раз, либо в строке 65, либо в строке 72, получаем (15) Р = Н + Я = количество различных элементов во вводе. (См, соотношения (8).) Если немного поразмыслить, это очевидным образом сле- дует также из строки 80. И, наконец, из строки 85 видно, что (16) о' = количество единичных циклов в выводе. С + з + 5 = (В + С) (Р + 1), (17) связывающее неизвестные С и 1,.
К счастью, время выполнения (7) — это функция отС+7 (так каконо включаетслагаемые" +ЗР+4С "+ЗК+47+" =."+76+ + 71 + "), поэтому нам не нужно больше пытаться анализировать величины С и 1, по отдельности. Просуммировав все эти результаты, находим, что общее время выполнения программы без учета времени, затрачиваемого на операции ввода-вывода, равно (18) (112НЛ' + 304Х вЂ” 2М вЂ” Г + 11С + 2à — 11) и. В этой формуле были использованы новые обозначения для характеристик данных: Л' — количество 1' — количество М вЂ” количество Х вЂ” количество Н вЂ” количество à — количество перфокарт ввода; непустых полей во вводе (исключая конечное "="); циклов во вводе; имен различных элементов во вводе; циклов в выводе (включая единичные циклы); единичных циклов в выводе.
(19) Очевидно. что величины В, С, Н, 7, Р и Я, которые мы сейчас интерпретировали как независимые параметры, влияют на время выполнения программы А. Теперь остается проанализировать только неизвестные С и Ь. Для этого придется проявить немного больше изобретательности. Просмотры входной информации, которые начинаются в строках 41 и 74, всегда заканчиваются либо в строке 47 (прошлый раз), либо в строке 80. В течение каждого из этих Р + 1 циклов команда "1303 1" выполняется В + С раз.
Это имеет место только в строках 44, 68 и 77, поэтому получаем нетривиальное соотношение Таблица 2 пеРеынбжение пеРеОтлнОВОк зл ОДин пРОхОД (акУд)(Ьсе)(аее)(УаИе)(ЬдУае) а -> ННаааааааааааННв'еес(есееееееаа Ь -+ ссссссссддддддддддддддддЬЬЬЬЬ с -+ ееееивес(йсссссссссссссссссссс +ддддддд)))дд)))ЬЬЬЬЬННЫНННННИ е -+ ЬЬЬЬ66Ь66ЬЬ6Ь6аеа))))6Ь)))))е 1 -э 1111еееееееееееессаааааааа111 д -+ е ) ) ) ) 11111111111111111111д д д д Следовательно, можно сделать вывод, что анализ такой программы, как А, во многих отношениях подобен решению занимательной головоломки. Ниже мы покажем,что если на выходе предполагается получить случайную перестановку, то средние величин (У и г' будут равны Нм и 1 соответственно.
Другой подход. Алгоритм А перемножает перестановки почти так же, как это обычно делают люди. Часто оказывается, что задачи, решаемые с помощью компьютера, очень похожи на те, с которыми люди постоянно сталкивались в течение долгих лет. Поэтому освященные веками методы решения, разработанныс для простых смертных, таких, как мы с вами, подходят и для компьютерных алгоритмов.
Но не менее часто приходится иметь дело с новыми методами, которые идеально подходят для компьютера, но совершенно непригодны для человека. Главная причина этого состоит в том, что компьютер "думает" по-другому; тип его памяти, г помощью которой он запоминает информацию, отличается от типа памяти человека.
Это различие можно проследить на примере нашей задачи перемножения перестановок. Используя приведенный ниже алгоритм, компьютер может выполнить умножение перестановок "одним махом", запоминая текущее состояние перестановки в целом по мере перемножения циклов. Предназначенный для человека алгоритм А просматривает формулу много раз, по одному для каждого элемента вывода, в то время как новый алгоритм делает все за один проход. Ното эарсепэ на такое вряд ли способен. Что представляет собой предназначенный для компьютера метод перемножения перестановок? Главная идея проиллюстрирована в табл. 2.
В столбце, распссюженном в этой таблице под каждым символом выражения, которое представлено в виде циклов, показано, какая перестановка выражена частичными циклами справа. Например, фрагмент формулы "... с( е)(6 д 1 а е)" представляет перестановку абсдеУд которая появляется в таблице под крайним справа символом И. Внимательно изучив табл. 2, можно понять принцип ее построения, если начать с тождественной перестановки справа и двигаться назад справа налево Столбец, расположенный под символом х, отличается от столбца справа (в котором записано предыдущее состояние) только строкой х; и новое значение в строке х — это значение, которое исчеэло в результате предыдущего изменения.
Короче говоря, имеем слелующий алгоритм. Алгоритм В (Перелсножение перестановок, представленных в виде циклов). Этот алгоритм (рис. 21) дает, в сущности, тот же результат, что и алгоритм А. Предположим, что переставляемыми элементами являются хы хт,..., х„. Будем использовать вспомогательную таблицу Т[1],Т[2],...,Т[п]; по окончании работы алгоритма х; переходит в х, в перестановке ввода тогда и только тогда, когда Т[г] = 1. В1.
[Инициализация.] Присвоить Т Я < — к, где 1 < Ь < п. Подготовиться также к просмотру справа налево. В2. [Следующий элемент.] Рассмотреть следующий элемент ввода (справа налево). Если ввод исчерпан, то работа алгоритма заканчивается. Если рассматривается элемент ")", то присвоить л +- О и повторить шаг В2; если это элемент "(", то перейти к шагу В4. В противном случае рассматриваетси элемент х; для некоторого 1; тогда перейти к шагу ВЗ.
ВЗ. [Замена Т[1].] Выполнить взаимный обмен Я ~+ Т[1]. Если в результате полу- чится Т[1] = О, то присвоить у +- 1. Вернуться к шагу В2. В4. [Замена Т[у].] Присвоить Т~Я +- Е (Здесь у — это строка, определяющая элемент ")" в обозначениях табл. 2, т. е. правую скобку, которая соответствует только что просмотренной левой скобке.) Вернуться к шагу В2. $ Рис.
21. Алгоритм Рн перемножение перестановок. Разумеется, после выполнения этого алгоритма необходимо еще вывести содержимое таблицы Т в циклическом виде; как будет показано ниже, это легко сделать методом "пометок". Теперь на основе нового алгоритма давайте напишем программу для М1Х. Будем придерживаться тех же основных правил, что и в программе А, используя такой же формат ввода и вывода, как и раньше. Но тут возникает небольшая проблема: как можно реализовать алгоритм В, не зная наперед, чему равны элементы хы хм..., х„? Неизвестно, чему равно и, а также будет ли элемент Ь равен х1'или хэ и т.
д. Существует простой способ решения данной проблемы — создать таблицу, внести в нее имена элементов, которые уже встречались, и каждый раз искать имя текущего элемента (см. строки 35-44 в программе ниже). Программа В (Дает тот оюе результат, чгпо и программа А). гХ = Е; г14 = г'; гП = Э; г13 = и, количество различных просмотренных имен.
ЕЦО 1200 ОВ1С е+ИАХИРЯ ОВ10 ь+ИАХЫРЯ ОВ10 е+ИАХМРБ ЕЦО РЕВИ ОВ1С а+24 01 ИАХМРБ 02 Х 08 Т 04 РЕВИ 05 АМЯ 06 ООТВОР 07 САВРБ ЕЦО 16 НЕТ 666 Совпадают со строками 05-22 программы А. ЕМТ1 АИЯ ЭЗЕ РОМЕ ЫАМ Х,З ЭАР ЯКТР СИРЗ Т,З ЭЕ ЯКХР МОЧЕ ЕРВЕИ МОЧЕ Х,З БТА Х,з 1 1 4) Я 8 Т Т Открыть цикл. Пометить имя.
84 85 1Н 86 87 В10НТ 88 ЯСАМ УУ 80 Э1 88 88 84 Э5 Эб 87 2Н 88 ЭУ 40 41 48 48 44 45 РООМР 46 47 48 40 50 51 1.ЕРТ 58 СТОИТЕ 58 54 ОСТРОТ 56 56 1Н 57 58 58 60 61 2Н 68 1МС2 16 ЕМТЗ 1 ЕИТХ 0 РЕС2 1 ЕРА РЕВИ,2 ЭАЕ ОТСЕЯ СИРА ВРВЕМ ЭЕ В1СНТ СИРА БРЕЕМ ЭЕ АЛЕЕТ ЕИТ4 1,3 ЯТА Х РЕС4 1 СИРА Х,4 ЭИЕ 2В 54Р РОСИО 1МСЗ 1 БТА Х,З БТЗ Т,З ЕМТ4 0,3 ЕРА Т,4 ЯТХ Т,4 ЯВС Я ЭАИЕ ЯСАМ ЕМТ1 0,4 ЭИР БСАИ БТХ Т,1 52Р ЯСАМ 1 1 А В В В С С В В Е Е Г Р Г б Н Н Н Н Э Э Э Э К К Е Р Максимальная длина ввода.
Таблица имен. Вспомогательная таблица состояния. Входная перестановка. Место для ответа. Место для печати. В этот момент г12 слов ввода находятся в РЕВИ, РЕВИ+ 1, ... и мы пока еще не видели нн одного имени. Присвоить Е +- О. В2. Сле юг ий элемент. Пропустить пробелы. Следующим элементом является ")'? Это "("? Приготовиться к поиску. Сохранить в начале таблицы, Искать в таблице имен.
Повторять до нахождения соответствия. Это имя появлялось ранее? Нет; увеличить размер таблицы. Вставить новое имя х„. Присвоить Т)и) +- п, 1 < — и. ВЗ. Замена Т)1), Сохранить Е Установить Е. Если Е было нулем, присвоить Э +- 1. В4. Замена Т)ль Вернуться к В2, если работа еще ие закончена. Весь ввод просмотрен.
Таблицы х и Т содержат ответ. Теперь построим циклическую запись. Имя было помечено? Это единичный цикл? СМР1 =АМБ= 65 64 65 66 67 БК1Р бб 69 70 РОМЕ ЕРЗ т,з ЕВАМ Х,З ЗАМ 2В М02Е ЗРЕЕМ РЕСЗ 1 ЗЗР 1В Т Найти элемент, в который переходит этот элемент. Т Т Он уже помечен? И' Да, цикл закрывается. Я Перейтн к следующему имени. Я 64 ЕЦРАЕБ АЕР 65 ЕМР ВЕС1М Строки 54 — б8, в которых строится циклическая запись на основании таблицы Т и таблицы имен, представляют собой небольшой алгоритм, который заслуживает внимания.
Величины А, В, ..., Н, 5, Т, И~, х, влияющие на время выполнения программы, конечно, отличаются от одноименных величин, которые использовались при анализе программы А. Анализ этих величин будет интересным упражнением для читателя (см. упр. 10). Опыт показывает, что основная часть времени выполнения программы В будет потрачена на поиск в таблице имен; это время определяется параметром Р. Существуют более эффективные алгоритмы поиска и построения словарей имен; они называются алгоритмами таблиц символов и играют важную роль в прикладной математике. В главе б мы займемся всесторонним исследованием эффективных алгоритмов таблиц символов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
