Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.), страница 10

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

В области разработки алгоритмов происходит такое же быстрое развитие, как и в других компьютерных технологиях. Возникает вопрос, действительно ли так важны алгоритмы, работающие на современных компьютерах, если и так достигнуты выдающиеся успехи в других областях высоких технологий, таких как: ° аппаратное обеспечение с высокими тактовыми частотами, конвейерной обработкой и суперскалярной архитектурой; ° легкодоступные, интуитивно понятные графические интерфейсы (О1Л); ° обьектно-ориентированные системы; ° локальные и глобальные сети. Ответ — да, безусловно. Несмотря на то, что иногда встречаются приложения, которые не требуют алгоритмического наполнения (например, некоторые простые %еЬ-приложения), для большинства приложений определенное алгоритмическое наполнение необходимо.

Например, рассмотрим %еЬ-службу, определяющую, как добраться из одного места в другое (во время написания книги существовало несколько таких служб). В основе ее реализации лежит высокопроизводительное аппаратное обеспечение, графический интерфейс пользователя, глобальная сеть и, возможно, обьекгно-ориентированный подход. Кроме того, для определенных операций, выполняемых данной %еЬ-службой, необходимо использование алгоритмов — например, таких как вычисление квадратных корней (что может потребоваться для определения кратчайшего пути), визуализации карт и интерполяции адресов.

Более того, даже приложение, не требующее алгоритмического наполнения на высоком уровне, сильно зависит от алгоритмов. Ведь известно, что работа приложения зависит от производительности аппаратного обеспечения, а при его разработке применяются разнообразные алгоритмы. Все мы также знаем, что Глава 1. Роль алгоритмов в вычислениях приложение тесно связано с графическим интерфейсом пользователя, а для разработки любого графического интерфейса пользователя требуются алгоритмы.

Вспомним приложения, работающие в сети. Чтобы они могли функционировать, необходимо осуществлять маршрутизацию, которая, как уже говорилось, основана на ряде алгоритмов. Чаще всего приложения составляются на языке, отличном от машинного. Их код обрабатывается компилятором или интерпретатором, которые интенсивно используют различные алгоритмы. И таким примерам нет числа.

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

Знание основных алгоритмов и методов их разработки — одна из характеристик, отличающих умелого программиста от новичка. Располагая современными компьютерными технологиями, некоторые задачи можно решить и без основательного знания алгоритмов, однако знания в этой области позволяют достичь намного большего. Упражнения 1.2-1. Приведите пример приложения, для которого необходимо алгоритмическое наполнение на уровне приложений, и дайте характеристику функций, входящих в состав этих алгоритмов.

1.2-2. Предположим, на одной и той же машине проводится сравнительный анализ реализаций двух алгоритмов сортировки, работающих по методу вставок и по методу слияния. Для сортировки п элементов методом вставок необходимо 8пз шагов, а для сортировки методом слияния — 64п 1б и шагов. При каком значении и время сортировки методом вставок превысит время сортировки методом слияния? 1.2-3. При каком минимальном значении п алгоритм, время работы которого определяется формулой 100пэ, работает быстрее, чем алгоритм, время работы которого выражается как 2", если оба алгоритма выполняются на одной и той же машине? Задачи 1-1. Сравнение времени работы алгоритмов Ниже приведена таблица, строки которой соответствуют различным функциям г" (и), а столбцы — значениям времени $. Определите максимальные значения и, для которых задача может быть решена за время 1, если Часть 1.

Основы 56 предполагается, что время работы алгоритма, необходимое для решения задачи, равно ! (и) микросекунд. Заключительные замечания Имеется множество учебников, посвященных общим вопросам, которые имеют отношение к алгоритмам. К ним относятся книги Ахо (АЬо), Хопкрофта (Норсгой) и Ульмана ((71!шап) [5,6], Бейза (Ваазе) и Ван Гельдера (Уап Ое16ег) [26], Брассарда (Вгаввап1) и Бретли (Вга!1еу) [46,47], Гудрича (Оотг(сЬ) и Тамазии (Татазз1а) [128], Горовица (Ногочч!!х), Сани (БаЬп1) и Раджисекарана (Ка]азекагап) [158], Кингстона (К]пйз!оп) [179], Кнута (Кпи1Ь) [182,183,185], Козена (Кожев) [193], Манбера (МапЬег) [210], Мельхорна (МеЬ1Ьош) [217,218,219], Пурдома (Рип1ош) и Брауна (Вготчл) [252], Рейнгольда (Ке!пйо16), Ньевергельта (Ы!ечегйе1!) и Део (Оео) [257], Седжевика (Яебйев1ск) [269], Скьены (Яс!ела) [280] и Вильфа (%!!1) [315].

Некоторые аспекты разработки алгоритмов, имеющие большую практическую направленность, обсуждаются в книгах Бентли (Веп11еу) [39,40] и Гоннета (Ооппе!) [126]. Обзоры по алгоритмам можно также найти в книгах Напс~ЬооИ о]' ТЬеогепса! Сотршег 5с!елсе, Ро!ите А [302] и СЯС НалйЬооК оп А!8огйЬть алс! ТЬеогу о!'Сотришг!оп [24]. Обзоры алгоритмов, применяющихся в вычислительной биологии, можно найти в учебниках Гасфилда (ОизбеЫ) [136], Певзнера (Речгпег) [240], Сетубала (Бе1иЬа!) и Мейдениса (МеЫап(в) [272], а также Вотермена (9!!а!еппап) [309]. ГЛАВА 2 Приступаем к изучению В этой главе мы ознакомимся с основными понятиями, с помощью которых на протяжении всей книги будет проводиться разработка и анализ алгоритмов. В начале главы исследуется алгоритм сортировки вставками.

Он предназначен для решения задачи сортировки, поставленной в главе 1. Для формулирования алгоритмов мы используем псевдокод (который должен быть понятен читателям, имеющим опыт программирования). Для каждого алгоритма обосновывается его корректность и анализируется время работы. В ходе анализа указанного алгоритма вводятся обозначения, используемые для указания зависимости времени работы алгоритма от количества сортируемых элементов. После обсуждения сортировки вставками описывается метод декомпозиции, основанный на принципе "разделяй и властвуй". Этот подход используется для разработки различных алгоритмов; в данном случае с его помощью будет сформулирован алгоритм, получивший название сортировки слиянием.

В конце главы анализируется время работы этого алгоритма сортировки. 2.1 Сортировка вставкой Наш первый алгоритм, алгоритм сортировки методом вставок, предназначен для решения задачи сортировки (зогйпд ргоЫеш), сформулированной в главе 1. Приведем еще раз эту формулировку. Вход: последовательность из и чисел (ам аз,...,а ).

Выход: перестановка (изменение порядка) (ама~з,...,а'„) входной последовательности таким образом, что для ее членов выполняется соотношение а' <а' < <а'„. 58 Часть 1. Основы Рнс. 2.1. Сортировка карт методом вставок Сортируемые числа также известны под названием ключи (кеуз). В этой книге алгоритмы обычно описываются в виде псевдокода, который во многих отношениях похож на языки программирования С, Рааса! и 1ача. Тем, кто знаком хотя бы с одним из этих языков, не потребуется много усилий на чтение алгоритмов. От обычного кода псевдокод отличается тем, что он выразителен, а также лаконично, точно и понятно описывает алгоритм.

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

Наше изучение алгоритмов начинается с рассмотрения сортяироаки встиавюй (шзеп1оп зоп). Этот алгоритм эффективно работает при сортировке небольшого количества элементов. Сортировка вставкой напоминает способ, к которому прибегают игроки для сортировки имеющихся на руках карт. Пусть вначале в левой руке нет ни одной карты, и все они лежат на столе рубашкой вверх. Далее со стола берется по одной карте, каждая из которых помещается в нужное место среди карт, которые находятся в левой руке.