Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 7
Текст из файла (страница 7)
Чаще всего приложения составляются на языке, отличном от машинного. Их код обрабатывается компилятором или интерпретатором, который интенсивно использует различные алгоритмы. И таким примерам несть числа. Кроме того, ввиду постоянного роста вычислительных возможностей компьютеров, они применяются для решения все более и более сложных задач. Как мы уже убедились на примере сравнительного анализа двух методов сортировки, с ростом сложности решаемой задачи различия в эффективности алгоритмов проявляются все значительнее.
Знание основных алгоритмов и методов их разработки — одна из характеристик, отличающих действительно умелого, опытного программиста от новичка. Располагая современными компьютерными технологиями, некоторые задачи можно решить и без основательного знания алгоритмов, однако знания в этой области позволяют достичь намного большего. Упражнения 1.2.1 Приведите пример приложения, для которого необходимо алгоритмическое наполнение на уровне приложений, и обсудите функции этих алгоритмов.
1.2.2 Предположим, на одной и той же машине проводится сравнительный анализ реализаций двух алгоритмов сортировки, работающих вставкой и слиянием. Для Часть Л Основы сортировки и элементов вставюй необходимо 8пз шагов, а для сортировки слиянием — 64п 18 и шагов. При каком значении и время сортировки вставкой превысит время сортировки слиянием? 1.2.3 При каком минимальном значении и алгоритм, время работы которого определяется формулой 100пз, работает быстрее, чем алгоритм, время работы юторого выражается как 2", если оба алгоритма выполняются на одной и той же машине? Задачи 1.1.
Сравнение времени работы алгоритмов Ниже приведена таблица, строки которой соответствуют различным функциям 1(п), а столбцы — значениям времени 0. Заполните таблицу максимальными значениями и, для которых задача может быть решена за время г, если предполагается, что время работы алгоритма, необходимое для решения задачи, равно 1" (и) микросекунд. Заключительные замечания Имеется множество отличных учебниюв, посвященных общим вопросам алгоритмов. К ним относятся книги Ахо (АЬо), Хопкрофта (Норсгой) и Ульмана (()!!шап) [5, 6]', Бейза (Ваазе) и Ван Гельдера (Чап Пе!бег) [27]; Брассарда (Вгаьаагд) и Брейтли (Впп!еу) [53]; Дасгупта (1лазйорГа), Пападимитроу (Рарагйгпйпоп) и Ваэирани (Чах!гап!) [81]; Гудрича (боодпсЬ) и Тамазии (Ташаьа(а) [147]; Гофри (Но(п) [174]; Горовитца (Ногоьу!Гх), Сани (80Ьш) и Раджасекарана (Гса]азейагап) [180]; Джонсонбауфа (1оЬпзопЬапйЬ) и Шефера (БсЬаеГег) [192]; гимеется русский перевод; А.
Аяо. Д, хоакрафт, Д. Ульмвн, струтануры оанныл н алгоритмы. — мл И Д. "Вильямс", 2000. 37 Глава !. Роль алгоритмов в вычисленшкс Кингстона [204]; Кляйнберга (К1ешЬег8) и Тардоса (Тап(оа) [207]; Кнута (Кпп1Ь) [208 — 210]2; Козена (Кохеп) [219]; Левитина (1.еизбп) [234]; Манбера (МапЪег) [241]; Мельхорна (МеЬ!Ього) [247-249]; Пурдома (Ршв(ош) и Брауна (Вгозип) [285]; Рейнгольда (КеупйоЫ), Ньевергельта ()ь)!еиег8е11) и Део (Оео) [291]; Седжевика (Бебйеххчс)с) [304]; Седжевика (Яебйеичс(с) и Флажоле (Р!а]01ег) [305]; Скьены (8!аепа) [3!6]; и Вильфа (чз7!!() [354]. Некоторые аспекты разработки алгоритмов, имеющие большую практическую направленность, обсуждаются в книгах Бентли (Веп1!еу) [41,42] и Гонне (Ооппе1) [144]. Обзоры по алгоритмам можно также найти в книгах Напс(ЬОО(с ОТ ТЬеогег!Са! Сотригег Бс(енсе, РЬ!ите А [340] и СКС А!8опгйзпв апз! ТЬеогу оТ Сотри!а!!Оп Напс(ЬОО(с [24].
Обзоры алгоритмов, применяющихся в вычислительной биологии, можно найти в учебниках Гасфилда (Опзйе!й) [155], Певзнера (Резгхпег) [273], Сетубала (БеШЪа1) и Мейданиса (МеЫашз) [308], а также Вотермана (%а1еппап) [348]. Имсечсв русский перевод ззпх книг: Д Кнуз. Искусство лрограммироеаяия, т. 3 Ослоеяыв алгоритмы. 3-е изд. — Мз И.Д. "Вильямс", 2000; Д. Кнут. искусство ярограммировалия. т.
2. Повучисзеялые аыоритмы, 3-е изд. — Мл И.Д. -Вильямс", 20ЗИ; Д. Кнут. Искусство программирования, т. 3. Сортировка и яоиск, 2-е изд.— Мс И.Д. "Вильямс", 2000. Кроме того, уме после написания данной книги вышел очередной зом "Иостстеа лрограммирмалия": Д. Кнут. Искусство лрограммироваякя, т. 4, и Коибияаторлые алгоритмы, часть 1.— Мз И.Д. "Внльвмст 2013. Глава 2.
Приступаем к изучению В этой главе аы ознакомитесь с основными понятиями, с помощью которых на протяжении всей книги будет проводиться разработка и анализ алгоритмов. Глава самодостаточна, но включает ряд ссылок на материал, который будет введен в главах 3 и 4 (в ней также имеются некоторые суммы, работа с которыми рассматривается в приложении А). В начале главы исследуется алгоритм сортировки вставками. Он предназначен для решения задачи сортировки, поставленной в главе 1. Мы определим "псевдокод", который должен быть понятен вам, если вы когда-либо занимались программированием, и применим его, чтобы показать, как будут определяться в книге наши алгоритмы. Определяя алгоритм сортировки вставкой, мы докажем его корректность и проанализируем время его работы. В ходе анализа вводятся обозначения, используемые для указания зависимости времени работы алгоритма от количества сортируемых элементов.
После обсуждения сортировки вставками описывается метод декомпозиции, основанный на принципе "разделяй и властвуй'*. Этот подход используется для разработки различных алгоритмов; в данном случае с его помощью будет сформулирован алгоритм, называемый сортировкой слиянием. В конце главы анализируется время работы этого алгоритма сортировки. 2.1.
Сортировка вставкой Наш первый алгоритм„алгоритм сортировки вставкой, предназначен для решения задачи совюиирввки, поставленной в главе 1. Вход. Последовательность и чисел (аы аз,..., а„). Выход. Перестановка (переупорядочение) (а1, а~э, ..., а'„) входной последовательности, такая, что а~1 < а~э < < а Сортируемые числа также известны под названием ключи ()сеуз). Хотя концептуально мы сортируем последовательность, входные данные мы получаем в виде массива с п элементами.
В этой книге алгоритмы обычно описываются в виде лсевдокода, который во многих отношениях похож на языки программирования С, С-н., 5ача, Ру~Ьоп или Рааса!. Тем, кто знаком хотя бы с одним из этих языков, не потребуется много Глава 2. Приетулаеи к изучению Ряе. 2.1. Сортировка карт вставкой.
усилий на чтение алгоритмов. От обычного кода псевдокод отличается тем, что он выразителен, а также лаконично, точно и понятно описывает алгоритм. Иногда в качестве таювого выступает литературный язык, поэтому не удивляйтесь, если в инструкции "настоящего" кода встретите обычную фразу или предложение. Другое различие между псевдокодом и обычным кодом заключается в том, что в псевдокоде, как правило, не рассматриваются некоторые вопросы, которые приходится решать разработчикам программного обеспечения.
Такие вопросы, как абстракция данных, модульность и обработка ошибок, часто игнорируются, чтобы более выразительно передать суть алгоритма. Наше изучение алгоритмов начинается с рассмотрения сарзяирааки всшавкай (1пкегбоп зог1). Этот алгоритм эффективно работает прн сортировке небольшого количества элементов. Сортировка вставкой напоминает способ, к которому прибегают игроки для сортировки имеющихся на руках карт. Пусть вначале в левой руке нет ни одной карты и все онн лежат на столе рубашкой вверх.
Далее со стола берется по одной карте, каждая из которых помещается в нужное место среди карт, которые находятся в левой руке. Чтобы определить, куда нужно поместить очередную карту, ее масть н достоинство сравниваются с мастью и достоинством карт в руке. Допустим, сравнение проводится в направлении слева направо (рнс. 2.1). В любой момент карты в левой руке будут отсортированы, и это будут те карты, которые первоначально лежали в стопке на столе. Псевдокод сортировки вставкой представлен ниже в виде процедуры под названием 1нзнктюм-йокт, которая получает в качестве параметра массив А[1 .. и), содержащий последовательность длиной и, которая должна быть отсортирована. (В коде количество элементов и в массиве А обозначается как А.1епд(л.) Алгоритм сортирует входные числа иа месгяе, без привлечения дополнительной памяти: она выполняет перестановку чисел в пределах массива А, и объем используемой при этом дополнительной памяти в любой момент работы алгоритма не превышает некоторую постоянную величину.
По завершении проце- Часть 2 Основы дуры 1)чзнкт)О)4-войт входной массив А содержит отсортированную выходную последовательность. 1)чзййт!О)ч-ЯОнт(А) 1 1ог5' = 2 (о А.1епд(й 2 )сеу = АЦ 3 // Вставка А[Я в отсортированную последовательность А[1 .. 3 — 1].
з =у — 1 ттййе з > О и А[з] > )сер А[1+1] = А[т] т=з — 1 А[а+ 1] = кеу 4 5 6 7 8 В начале каждой итерации цикла Ког, состояшего из строк 1-8, подмас- сив А[1..5 — 1] состоит из элементов, которые изначально находились в А[1 .. у — 1], но теперь расположены в отсортированном порядке. 1 2 3 4 5 б 1 2 3 4 5 б 1 2 3 4 5 б (а) гй.!Я 4 16 ~ 11 3 ) (6) .Дф~.,'[[(][[ ~6, 1 ) 3 1 (а) 2! 4 ('Й: 1 3, ау 1 2 3 4 5 6 (г) Г )[ 4:Г5'Гй 3 1 1 2 3 4 5 б (л) [ 1 ]-.21!)„Ф ~Д,~~;.
1 2 3 4 5 6 (с) 1 2 3 4 5 6 Рис. 2.2. Операции процедуры 1изнктгои-зонт над массивом А = (б, 2, 4, б, 3, 3). Элементы массива обозначены квадратиками, над которыми находятся индексы, а внутри — значения соответствующих элементов. Части (а)-(д) этого рисунка соответствуют итерациям цикла Гог в строках 1-8 псевдокода. В каждой итерации черный квадратик содержит значение ключа из А[Я, которое сравнивается со значениями серых квадратиков, расположенных слева от него (строка псевдокода 5).
Серыми стрелками указаны те значения массива„которые сдвигаются на одну позицию вправо (строка 6), а черной стрелкой — перемещение ключа (строка 8). В части (е) показано конечное состояние отсортированного массива. Инварианты цикла и корректность сортировки вставкой На рис. 2.2 показано, как этот алгоритм работает с массивом А = (о, 2, 4, 6, 1, 8). Индекс у указывает "текушую карту", которая помешается в руку. В начале каждой итерации цикла (ог с индексом 3 массив А состоит из двух частей. Элементы А[1 ..у — 1] соответствуют отсортированным картам в руке, а элементы А[) + 1..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
