Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 17
Текст из файла (страница 17)
в) С помощью условия завершения инварианта цикла, доказанного в пункте б, сформулируйте инвариант цикла (ог в строках 1-4, который бы позволил доказать неравенства (2.3). Доказательство должно иметь такую же структуру доказательства инварианта цикла, которая использовалась в аналогичных доказательствах в данной главе.
г) Определите время пузырьковой сортировки в наихудшем случае и сравните его со временем сортировки методом вставок. 2-3. Корректность правила Горнера В приведенном ниже фрагменте кода реализовано правило Горнера (Ногпег'з гп!е), позволяющее вычислить значение полинома Р (х) = ,') аьх в=о = ао+х(аз+х(аз+ +х(а„~+ха„)...)) по заданным коэффициентам ао, а1,..., а„и величине х: 1 у+ — 0 2 ( — п 3 иййег)0 4 шоу — а+х у 5 г~ — г — 1 а) Определите асимптотическое время работы приведенного выше фрагмента кода. б) Напишите псевдокод, реализующий алгоритм обычного вычисления полинома, когда каждое слагаемое полинома вычисляется отдельно. Глава 2.
Приступаем к изучению 85 Определите асимптотическое время работы этого алгоритма и сравните его со временем работы алгоритма, основанного на правиле Горнера. в) Докажите, что ниже сформулирован инвариант цикла н Ы1е в строках 3-5. В начале каждой итерации цикла зтЫ)е в строках 3-5 выполняется такое соотношение; я-(з+1) ь у = ~~) аь+з~1х . ь=о Суммирование по нулевому количеству слагаемых интерпретируется как О. Доказательство должно иметь такую же структуру доказательства инварианта цикла, которая использовалась в аналогичных доказательствах в данной главе. В ходе доказательства необходимо продемонстрировать, что по завершении алгоритма выполняется соотношение У = 2,'ь' оаьх .
и ь г) В заключение продемонстрируйте, что в приведенном фрагменте кода правильно вычисляется значение полинома, который задается коэффициентами ао, аы..., а„. 2-4. Инверсии Предположим, что А [1..п) — это массив, состоящий из и различных чисел. Если г ( з и А [г] ) А [Я, то пара (г, у) называется инверсией (1лчегз(ол) в массиве А. а) Перечислите пять инверсий, содержащихся в массиве (2, 3, 8, б, 1). б) Сконструируйте массив из элементов множества (1,2,..., и), содержащий максимальное количество инверсий. Сколько инверсий в этом массиве? в) Какая взаимосвязь между временем сортировки методом вставок и количеством инверсий во входном массиве? Обоснуйте ваш ответ.
г) Сформулируйте алгоритм, определяющий количество инверсий, содержащихся в произвольной перестановке и элементов, время работы которого в наихудшем случае равно О (и 18п). (Указание: модифицируйте алгоритм сортировки слиянием.) Часть 1. Основы 86 Заключительные замечания В 1968 году Кнут (Кпц!)з) опубликовал первый из трех томов, объединенных названием ТЬе Аг! о)" Сопгришг Рго8гал1тт8 (Искусство программирования) (182,183,185). Этот том стал введением в современные компьютерные алгоритмы с акцентом на анализе времени их работы, а весь трехтомник до сих пор остается интереснейшим и ценным пособием по многим темам, представленным в данной книге.
Согласно Кнуту, слово "алгоритм" происходит от имени персидского математика девятнадцатого века аль-Хорезми (а!-КЬо~чаг1гтш). Ахо (АЬо), Хопкрофт (Норсгой) и Ульман (!)йшап) !51 являются сторонниками асимптотнческого анализа алгоритмов, являющегося средством сравнения нх относительной производительности. Они также популяризируют применение рекуррентных соотношений для описания времени работы рекурсивных алгоритмов. Кнут (185) с энциклопедической полнотой рассмотрел многие алгоритмы сортировки. Его сравнение алгоритмов сортировки включает в себя подробный анализ с точным подсчетом шагов, подобный тому, что был проведен в этой книге для сортировки методом вставок.
В ходе обсуждения Кнутом алгоритма сортировки вставкой приводится несколько вариаций этого алгоритма. Важнейшей нз них является сортировка по Шеллу (!3Л.. Б!зе11), который использовал сортировку методом вставок для упорядочения периодических последовательностей, чтобы получить более производительный алгоритм сортировки. В книге Кнута также описана сортировка слиянием. В книге упоминается, что в !938 году была создана механическая машина, способная за один проход объединять две стопки перфокарт. По всей видимости, первым программу для сортировки методом слияния (предназначенную для компьютера Е!3УАС) в 1945 году разработал Джон фон Нейман ().
акоп Нешпапп), который был одним из первых создателей теории вычислительных машин. Ранние этапы развития в области доказательства корректности программ описаны Гризом (ОПез) !1331, который считает, что первая статья по этой теме была написана Науром (Р. Ыацг).
Авторство понятия инварианта цикла Гриз приписывает Флойду (К.%. Р!оуд). В учебнике Митчелла (М!гсЬе!1) !2221 описывается прогресс, достигнутый в области доказательства корректности программ в настоящее время. ГЛАВА 3 Рост функций Определенный в главе 2 порядок роста, характеризующий время работы алгоритма, является наглядной характеристикой эффективности алгоритма, а также позволяет сравнивать производительность различных алгоритмов. Если количество сортируемых элементов п становится достаточно большим, производительность алгоритма сортировки по методу слияний, время работы которого в наихудшем случае возрастает как 9 (и1дп), становится выше производительности алгоритма сортировки вставкой, время работы которого в наихудшем случае возрастает как О (пз).
Несмотря на то, что в некоторых случаях можно определить точное время работы алгоритма, как это было сделано для алгоритма сортировки методом вставок в главе 2, обычно не стоит выполнять оценку с большой точностью. Для достаточно больших входных данных постоянные множители и слагаемые низшего порядка, фигурирующие в выражении для точного времени работы алгоритма, подавляются эффектами, вызванными увеличением размера ввода. Рассматривая входные данные достаточно больших размеров для оценки только такой величины, как порядок роста времени работы алгоритма, мы тем самым изучаем асимптотическую эффективность алгоритмов.
Это означает, что нас интересует только то, как время работы алгоритма растет с увеличением размера входных данных в пределе, когда этот размер увеличивается до бесконечности. Обычно алгоритм, более эффективный в асимптотическом смысле, будет более производительным для всех входных данных, за исключением очень маленьких.
В этой главе приведено несколько стандартных методов, позволяющих упростить асимптотический анализ алгоритмов. В начале следующего раздела вводится несколько видов "асимптотических обозначений*', одним из которых являются уже известные нам О-обозначения. Далее представлены некоторые соглашения Часть 1. Основы по поводу обозначений, принятых в данной книге. Наконец, в завершающей части главы рассматривается поведение функций, часто встречающихся при анализе алгоритмов. 3.1 Асимптотические обозначения Обозначения, используемые нами для описания асимптотического поведения времени работы алгоритма, используют функции, область определения которых— множество неотрицательных целых чисел Х = (О, 1, 2,...).
Подобные обозначения удобны для описания времени работы Т (п) в наихудшем случае, как функции, определенной только для целых чисел, представляющих собой размер входных данных. Однако иногда удобно изменить толкование асимптотических обозначений тем илн иным образом. Например, эти обозначения легко обобщаются на область действительных чисел или, наоборот, ограничиваются до области, являющейся подмножеством натуральных чисел.
При этом важно понимать точный смысл обозначений, чтобы изменение толкования не привело к неверному их использованию. В данном разделе вводятся основные асимптотические обозначения, а также описывается, как чаще всего изменяется их толкование. О-обозначения В главе 2 было показано, что время работы алгоритма сортировки методом вставок в наихудшем случае выражается функцией Т (и) = 9 (пз). Давайте разберемся в смысле данного обозначения. Для некоторой функции д (и) запись 8 (д (и)) обозначает множество функций (,(' (и): существуют положительные константы сы сз и по 0(д(п)) = 1 такие что О < с1д (и) < )' (ть) < сад (и) для всех п > по Функция г" (и) принадлежит множеству О (д (и)), если существуют положительные константы с1 и сз, позволяющие заключить эту функцию в рамки между функциямн сад(ть) и сад(п) для достаточно больших п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
