работы в этой компании.

Многие наши коллеги использовали предварительные варианты этой книги в своих лекционных курсах, и предложили различные улучшения. Мы хотели бы особенно поблагодарить следующих наших коллег: Richard Beigel (Yale), Andrew Goldberg (Stanford), Joan Lucas (Rutgers), Mark Overmars (Utrecht), Alan Sherman (Tufts, Maryland), Diane Souvaine (Rutgers).

При чтении лекций по материалам этой книги нам помогали наши коллеги, которые внесли много улучшений. Мы особенно признательны: Alan Baratz, Bonnie Berger, Aditi Dhagat, Burt Kaliski, Arthur Lent, Andrew Moulton, Marios Papaefthymiou, Cindy Phillips, Mark Reinhold, Phil Rogaway, Flavio Rose, Arie Rudich, Alan Sherman, Cliff Stein, Susmita Sur, Gregory Troxel, Margaret Tuttle.

Многие люди помогли нам в работе над книгой в разных отношениях: работа в библиотеке (Denise Sergent), гостеприимство в читальном зале (Maria Sensale), доступ к личной библиотеке (Albert Meyer), проверка упражнений и придумывание новых (Shlo-mo Kipnis, Bill Niehaus, David Wilson), составление индекса (Marios Papaefthymiou, Gregory Troxel), техническая помощь (Inna Radzi-hovsky, Denise Sergent, Gayle Sherman, и особенно Be Hubbard).

Многие ошибки обнаружили наши студенты, особенно Bobby Blumofe, Bonnie Eisenberg, Raymond Johnson, John Keen, Richard Lethin, Mark Lillibridge, John Pesaris, Steve Ponzio, Margaret Tuttle.

Многие наши коллеги сообщили нам полезную информацию о конкретных алгоритмах, а также критически прочитали отдельные главы книги; в их числе Bill Aiello, Alok Aggrawal, Eric Bach, Vasek Chvatal, Richard Cole, Johan Hastad, Alex Ishii, David Johnson, Joe Kilian, Dina Kravets, Bruce Maggs, Jim Orlin, James Park, Thane Plambeck, Herschel Safer, Jeff Shallit, Cliff Stein, Gil Strang, Bob Tar-jan, Paul Wang. Многие из них предложили нам задачи для нашей книги, среди них Andrew Goldberg, Danny Sleator, Umesh Vazirani.

Английский оригинал книги был подготовлен с помощью Р/ГХ (макропакет для системы TgX). Рисунки делались на компьютере Apple Macintosh с помощью программы Mac Draw II; мы благодарны за оперативную техническую поддержку в этой области (Joanna Terry, Claris Corporation; Michael Mahoney, Advanced Computer Graphics). Индекс был подготовлен с помощью программы Windex, написанной авторами. Список литературы готовился с помощью программы ВшТеХ. Оригинал-макет английского издания был подготовлен в Американском математическом обществе с помощью фотонаборной машины фирмы Autologic; мы признательны за помощь в этом (Ralph Youngen, Американское математическое общество). Макет разработали: Rebecca Daw, Amy Henderson (реализация макета для системы ЖГ[Х), Jeannet Leendertse (обложка).

Авторы получили большое удовольствие от сотрудничества с издательствами MIT Press (Frank Sallow, Terry Ehling, Larry Cohen,

Lorrie Lejeune) и McGraw-Hill (David Shapiro) и благодарны им за поддержку и терпение, а также замечательное редактирование (Larry Cohen).

Наконец, авторы благодарят своих жён (Nicole Cormen, Lina Lue Leicerson, Gail Rivest) и детей (Ricky, William и Debby Leicerson; Alex и Christopher Rivest) за любовь и поддержку при работе над книгой (Alex Rivest также помог нам с «парадоксом дней рождения на Марсе» (раздел 6.6.1). Любовь, терпение и поддержка наших семей сделали эту книгу возможной; им она и посвящается.

Кембридж,Томас Кормен (Thomas Н. Cormen)

МассачусетсЧарльз Лейзерсон (Charles Е. Leiserson)

март 1990 годаРональд Ривест (Ronald L. Rivest)

От переводчиков:

Мы признательны издательству MIT и авторам за разрешение перевести книгу, и за помощь при подготовке перевода (в том числе за предоставление английского текста книги и иллюстраций в электронной форме). Издание перевода стало возможно благодаря финансовой поддержке Российского фонда фундаментальных исследований (руководитель проекта В.А. Успенский).

В работе над переводом книги участвовала большая группа студентов, аспирантов и сотрудников Московского центра непрерывного математического образования, Независимого Московского университета и МГУ:

К. Белов, Ю. Боравлёв, Д. Ботин, В. Горелик, Д. Дерягин Ю. Калнишкан, А. Катанова, С. Львовский, А. Ромащенко, К. Со-нин, К. Трушкин, М. Ушаков, А. Шень, В. Шувалов, М. Юдашкин (перевод)

A.Акимов, М. Вьюгин, Д. Дерягин, А. Евфимьевский, Ю. Калнишкан, А. Ромащенко, А. Чернов М. Ушаков, А. Шень (редактирование)

B.Радионов (вёрстка) В.В. Ященко (редактор)

1Введение

В этой главе мы разбираем основные понятия и методы, связанные с построением и анализом алгоритмов, на примере двух алгоритмов сортировки - простейшего алгоритма сортировки вставками и более эффективного алгоритма сортировки слиянием.

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

Алгоритм (algorithm) - это формально описанная вычислитель-

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

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

В этой главе мы рассматриваем задачу сортировки (sorting problem); помимо своей практической важности эта задача служит удобным примером для иллюстрации различных понятий и методов. Она описывается так:

Вход: Последовательность п чисел (ai, 0,2, , ап).

Выход: Перестановка (al5 а2,..., ап) исходной последовательности, для которой at а2 ... ап.

Например, получив на вход (31,41,59,26,41,58), алгоритм сортировки должен выдать на выход (26,31,41,41,58,59).

Подлежащая сортировке последовательность называется входом (instance) задачи сортировки.

1.1. Алгоритмы

ная процедура, получающая исходные данные