1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 2
Текст из файла (страница 2)
О пользовании книгой пэвдислоэив Эта книга задумана как начальный курс по разработке и анализу алгоритмов. Основной упор сделан на идеи и простоту понимания, а не на проработку деталей реализации или программистские трюки. Часто вместо длинных утомительных доказательств даются лишь неформальные интуитивные объяснения. Книга замкнута в себе и не предполагает специальной подготовки ни по математике, ни по языкам программирования. Однако желательна определенная зрелость в навыках обращения с математическими понятиями, а также некоторое знакомство с языками программирования высокого уровня, такими, как Фортран или Алгол. Для полного понимания гл.
6 — 8 и 12 нужны некоторые познания в линейной алгебре. Эта книга использовалась как основа для спецкурсов по разработке алгоритмов. За один семестр изучался материал, покрывающий ббльшую часть гл. 1 — 5, 9 и 10 вместе с беглым обзором тематики остальных глав. Во вводных курсах основное внимание уделялось материалу из гл.
1 — 5, но равд. 1.6, !.7, 4.13, 5.11 и теорема 4.5 обычно не изучались. Книгу можно также использовать для более глубоких спецкурсов, делая упор на теорию алгоритмов. Основой для этого могли бы служить гл. 6 — 12. В конце каждой главы приведены упражнения, обеспечивающие преподавателя широким выбором домашних заданий. Упражнения классифицированы по трудности. Упражнения без звездочек годятся для вводных курсов; упражнения с одной звездочкой труднее, а с двумя — еще труднее. В замечаниях по литературе в конце каждой главы делается попытка указать печатный источник для каждого алгоритма и результата, содержащихся в тексте и упражнениях.
Благодарности Материал книги основан на набросках лекций для курсов, читавшихся авторами в Корнеллском и Принстонском университетах и в Стивенсонском технологическом институте. Авторы хотели бы поблагодарить многих людей, которые критически прочитали различные части рукописи н внесли полезные предложения. Особенно мы хотели бы поблагодарить Келлога Бута, Стана Брауна, Стива Чена, Алена Сайфера, Арча Дейвиса, Майка Фишера, Хейнию Гаевску, Майка Гэри, 1Одая Гупту, Майка Харрисона, Матта Хекта, Гарри Ханта, Дейва Джонсона, Марка Каплана, Дона Джонсона, Стива Джонсона, Брайана Кернигана, Дона Кнута, Ричарда Лэднера, Аниту Ла-Саль, Дуга Мак-Илроя, Альберта Мейера, Кристоса Пападимитриу, Билла Плогера, Джона Сэвиджа, Ховарда Зигеля, Кена Стейглнца, Лэрри Стокмейера, Тома Жимански и Теодора Ена.
ПРЕДИСЛОВИЕ Мы выражаем особую благодарность Джеме Карневейл, Полине Камерон, Ханне Крессе, Эдит Персер и Руфи Сузуки за быструю и качественную перепечатку рукописи. Авторы также благодарны фирме ВеН ЬаЬога1ог1ез и университетам Корнеллскому, Принстонскому и Калифорнийскому (отделение в Беркли) за предоставленные возможности для подготовки рукописи. Июнь 1974 Альфред Ахо Джон Хопкрофт Джефри Улыбин МОДЕЛИ ВЫЧИСЛЕНИЙ Если дана задача, как найти для ее решения эффективный алгоритм? А если алгоритм найден, как сравнить его с другими алгоритмами, решающими ту же задачу? Как оценить его качество? Вопросы такого рода интересуют и программистов, и тех, кто занимается теоретическим исследованием вычислений, В этой книге мы изучим различные подходы, с помощью которых пытаются получить ответ на вопросы, подобные перечисленным.
В настоящей главе рассматриваются несколько моделей вычислительной машины — машина с произвольным доступом к памяти, машина с произвольным доступом к памяти и хранимой программой и машина Тьюринга. Этн модели сравниваются по их способности отражать сложность алгоритма, и на их основе строятся более специализированные модели вычислений, а именно: неветвящиеся арифметические программы, битовые вычисления, вычисления с двоичными векторами и деревья решений. В последнем разделе этой главы вводится язык для описания алгоритмов, называемый Упрощенным Алголом. 1.1.
АЛГОРИТМЫ И ИХ СЛОЖНОСТИ Для оценки алгоритмов существует много критериев. Чаще всего нас будет интересовать порядок роста необходимых для решения задачи времени и емкости памяти при увеличении входных данных. Нам хотелось бы связать с каждой конкретной задачей некоторое число, называемое ее размером, которое выражало бы меру количества входных данных. Например, размером задачи умножения матриц может быть наибольший размер матриц-сомножителей. Размером задачи о графах может быть число ребер данного графа. Время, затрачиваемое алгоритмом, как функция размера задачи, называется временнбй сложностью этого алгоритма, Поведение этой сложности в пределе при увеличении размера задачи называется асимптотической временнбй сложностью.
Аналогично можно опре- 11 гл. ь модели вычисления делить емкостную сложность и асимптотическую емкостную сложность. Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. Если алгоритм обрабатывает входы размера и за время сп', где с — некоторая постоянная, то говорят, что временная сложность этого алгоритма есть 0(п*) (читается "порядка и"), Точнее, говорят, что (неотрицательная) функция д(п) есть 0(у(п)), если существует такая постоянная с, что у(п)(с)(п) для всех, кроме конечного (возможно, пустого) множества, неотрицательных значений и. Можно было бы подумать, что колоссальный рост скорости вычислений, вызванный появлением нынешнего поколения цифровых вычислительных машин, уменьшит значение эффективных алгоритмов.
Однако происходит в точности противоположное. Так как вычислительные машины работают все быстрее и мы можем решать все ббльшие задачи, именно сложность алгоритма определяет то увеличение размера задачи, которое можно достичь с увеличением скорости машины. Допустим, у нас есть пять алгоритмов А,— А, со следующими временными сложностями: Алгоритм Временная сложность А, и А, и 1од и') А, и' А, и' А, 2а Здесь временная сложность — это число единиц времени, требуемого для обработки входа размера и. Пусть единицей времени будет одна миллисекунда. Тогда алгоритм А, может обработать за одну секунду вход размера 1000, в то время как А, — вход размера не более 9. На рис. 1.1 приведены размеры задач, которые можно решить за одну секунду, одну минуту и один час каждым из этих пяти алгоритмов.
Предположим, что следующее поколение вычислительных машин будет в 1О раз быстрее нынешнего. На рис. 1.2 показано, как возрастут размеры задач, которые мы сможем решить благодаря этому увеличению скорости. Заметим, что для алгоритма А, десятикратное увеличение скорости увеличивает размер задачи, которую можно решить, только на три, тогда как для алгоритма А, размер задачи более чем утраивается. Вместо эффекта увеличения скорости рассмотрим теперь эффект применения более действенного алгоритма.
Вернемся к рис. 1.1. ') Если не оговорено противное, все логарифмы в втой книге берутся по основанню 2. !.!. АЛГОРИТМЫ И ИХ СЛОЖНОСТИ Максимальный размер задачи Временная длгори™ сложность 1 с 1 мин 1 ч А, Аь А, А, Аь 1000 !40 31 1О 9 6Х !Оь 4893 244 39 15 3,6 х! О' 2,0х!О' 1897 153 2! л л 1оял л' ль Рис. !.!. Гранины размерон задач, определяемые скоростыю роста сложности. Максимальный размер задачи Временная сложность Алгоритм до ускорения после ускорения А, А, !Оя, Примерно 1Озь для больших зз 3,16зь 2,15з, я!+ 3,3 л1ойл ль л' 2И '!ь Аь А, Яь Яь зь Рис.
1хн Эффект десятикратного ускорения. 13 Если в качестве основы для сравнения взять 1 мин, то, заменяя алгоритм А, алгоритмом А „можно решить задачу, в 6 раз большую, а заменяя А, на А„можно решить задачу, большую в !25 раз. Зги результаты производят гораздо большее впечатление, чем двукратное улучшение, достигаемое за счет десятикратного увеличения скорости. Если в качестве основы для сравнения взять 1 ч, то различие оказывается еще значительнее. Отсюда мы заключаем, что асимптотическая сложность алгоритма служит важной мерой качественности алгоритма, причем такой мерой, которая обещает стать еще важнее при последующем увеличении скорости вычислений. Несмотря на то что основное внимание здесь уделяется порядку роста величин, надо понимать, что большой порядок роста сложности алгоритма может иметь меньшую мультипликативную посто- гл.
ь модели вычислении янную, чем малый порядок роста сложности другого алгоритма. В таком случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для задач с малым размером — возможно, даже для всех задач, которые нас интересуют.
Например, предположим, что временные сложности алгоритмов А„А„А„А, н А, в действительности равны соответственно 1000и, 1ООа 1оя и, 1Оп', и' и 2". Тогда А, будет наилучшим для задач размера 2<и<9, А,— для задач размера 10<п<58, А,— при 59<э<1024, а А,— при п)1024. Прежде чем продолжать обсуждение алгоритмов и их сложностей, мы должны точно определить модель вычислительного устройства, используемого для реализации алгоритмов, а также условиться, что понимать под элементарным шагом вычисления.
К сожалению, нет такой вычислительной модели, которая была бы хороша во всех ситуациях. Одна из основных трудностей связана с размером машинных слов. Например, если допустить, что машинное слово может быть целым числом произвольной длины, то всю задачу можно закодировать одним числом в виде одного машинного слова. Если же допустить, что машинное слово имеет фиксированную длину, то возникают трудности даже просто запоминания произвольно больших чисел, не говоря уже о других проблемах, которые часто удается обойти, если решаются задачи скромного размера. Для каждой задачи надо выбирать подходящую модель, которая точно отразит действительное время вычисления на реальной вычислительной машине.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
