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

а Сделайте заключение, что в приведенном фрагменте кода правильно вычисля- ется значение полинома, который задается коэффициентами ао, аз,..., а„. Глава 2. Прнстулаем к изучению 2.4. Инверсии Пусть А[1 .. п] представляет собой массив из и различных чисел. Если з с з и А(з] > А[2], то пара (з, з) называется инверсией А. а Перечислите пять инверсий массива (2,3,8,6,1). 6. Каюй массив из элементов множества (1, 2,..., и) содержит максимальное количество инверсий? Сюлъю инверсий в этом массиве? в. Какая существует взаимосвязь между временем сортировки методом вставок и юличестаом инверсий во входном массиве? Обоснуйте свой ответ.

а Разработайте алгоритм, определяющий количество инверсий, содержащихся в произвольной перестановке и элементов, время работы которого в наихудшем случае равно гЭ(п 18 и). (Указание: модифицируйте алгоритм сортировки слиянием.) Заключительные замечания В 19б8 году Кнут (Клпбз) опубликовал первый из трех томов, объединенных названием т)зе Аи ог Сотригег Ригйгаттгнй (Искусство программирования) [208- 210]".

Этот первый том стал введением в современные компьютерные алгоритмы с акцентом на анализе времени нх работы, а весь трехтомник до сих пор остается интереснейшим н ценнейшим пособием по многим темам, представленным в данной книге. Согласно Кнуту, слово "алгоритм" происходит от имени персидского математика )Х века аль-Хорезми (а1-КЬоьвалзш1).

Ахо (АЬо), Хопкрофт (Норсгой) и Ульман (\ЛЬпап) [5] являются сторонниками асимптотнчесюго анализа алгоритмов (с использованием обозначений, вводимых в главе 3, включая О-обозначения), являющегося средством сравнения их относительной производительности. Они также популярнзируют применение рекуррентных соотношений для описания времени работы рекурсивных алгоритмов. Кнут [210] с энциклопедичесюй полнотой рассмотрел многие алгоритмы сортировки.

Его сравнение алгоритмов сортировки включает в себя подробный анализ с точным подсчетом шагов, подобный проведенному в этой книге для сортировки методом вставок. В ходе обсуждения Кнутом алгоритма сортировки вставкой приводится несколько вариаций этого алгоритма. Важнейшей из них является сортировка Д.Л. Шелла (ПЛ..

8Ьей), который использовал сортировку методом ггИмеется руссклй перемю зтнх книг: Д. Кнут. Нскусстю лрограммлроволал, т. 1. Ословлыг азгорлтмы. 1-е юд. — Мг И.Д. "Вильямс", 2000; Д. Кнут. Искусство лрогрхммлровалкя, т. 2. Паьучаслеллме алгоратмы, 1-е лзд. — Мз И.Д. "Внлькмс? 2000; Д. Кнут. Искусство лрограммщювалня, т. 1. Сортировка ч ленск, 2-е юд.— Мз И,Д.

"Внльямсз 2000. Кроме того, уме после непнсення данной кннгн вымел очерелной том тнсяэсслма лрограммнювалая": Д. Кнут. Искзсство лрсграмчщювалая, т. й Х Камбаяаторлые алгоритмы, часть 1.— Мг ИЛ "Вюмвмс", 2013. з звк згзз бб Часть а Основы вставок для упорядочения периодических подпоследовательностей, чтобы получить более производительный алгоритм сортировки.

В книге Кнута также описана сортировка слиянием. В ней же упоминается, что в 1938 году была создана механическая машина, способная за один проход объединять две стопки перфокарт. По всей видимости, первым программу для сортировки методом слияния (предназначенную для компьютера Е1УЧАС) в 1945 году разработал Джон фон Нейман (в. чоп Ыепшапп), который был одним из создателей теории вычислительных машин. Ранние этапы развития в области доказательства корректности программ описаны Гризом (Свпез) 11521, который считает, что первая статья по этой теме была написана П.

Науром (Р. Хаог). Авторство понятия инварианта цикла Гриз приписывает Р. Флойду (К. %. Р!суд). В учебнике Митчелла (М11спе11) [254) описывается прогресс, достигнутый в области доказательства корректности программ в настоящее время. Глава 3. Рост функций Определенный в главе 2 порядок роста, характеризующий время работы алгоритма, является наглядным показателем эффективности алгоритма, а также позваляет сравнивать производительность различных алгоритмов. Если количество сортируемых элементов п становится достаточно большим, производительность алгоритма сортировки по методу слияний, время работы которого в наихудшем случае возрастает как Й(п )к и), становится выше производительности алгоритма сортировки вставкой, время работы которого в наихудшем случае возрастает как 6(п ). Несмотря на то что в некоторых случаях можно определить точное время работы алгоритма, как это было сделано для алгоритма сортировки методом вставок в главе 2, обычно не стоит тратить лишние усилия для получения оценки с высокой точностью.

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

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

Часть 6 Основы 3.1. Аеимптотические обозначения Обозначения, используемые нами для описания асимптотического поведения времени работы алгоритма, используют функции, областью определения которых является множество неотрицательных целых чисел )з = (0,1,2,...). Подобные обозначения удобны для описания времени работы Т(п) в наихудшем случае как функции, определенной только для целых чисел, представляюших собой размер входных данных. Однако иногда удобно изменить толювание асимптотических обозначений тем или иным не совсем корректным образом. Например, можно распространить эти обозначения на действительные числа или, наоборот, ограничить их областью, являющейся подмножеством натуральных чисел.

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

Однако фактически асимптотические обозначения применяются к функциям. Вспомним, что мы охарактеризовали время работы сортировки вставкой в наихудшем случае как апз + 6п + с для некоторых констант а, 6 и с. Записывая время работы сортировки вставкой как 9(пз), мы абстрагируемся от некоторых деталей этой функции. Поскольку асимптотические обозначения применимы к функциям, то то, что мы записываем просто как 9(п ), представляет собой функцию ап + Ьп+ с, которая в данном случае, помимо прочего, описывает время работы сортировки вставюй в наихудшем случае. В этой книге функции, к которым мы применяем асимптотические обозначения, обычно характеризуют время работы алгоритма.

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

Другими словами, часто желательно получить всеобъемлющее утверждение, охватывающее все варианты входных данных, а не только наихудший случай. Мы познакомимся с асимптотическими обозначениями, которые хорошо подходят для характеристики времени выполнения безотносительно ко входным данным. бд Глава 3. Рост функций ев-обозначения В главе 2 было показано, что время работы сортировки вставкой в наихудшем случае составляет Т(п) = ез(пз). Давайте разберемся в смысле данного обозначения. Для заданной функции д(п) запись ез(д(п)) обозначает множество функций ()(д(п)) = (У(п): сугцествуют положительные константы сы сз и пс, такие, что О < с)д(п) < у(п) < сзд(п) для всех и ~ по) Функция з (и) принадлежит множеству ез(д(п)), если существуют положительные константы с) н сз, такие, что при достаточно больших и эта функция может быль заключена в рамки между с)д(п) и сад(п).