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

Стоимость каждого из двух подузлов на втором уровне рекурсии равна сп/2. Мы продолжаем раскрывать каждый узел дерева, разбивая его на составные части, определяемые рекуррентным соотношением, пока размеры задач не достигнут значений 1, со стоимостью с. В части (г) показано получающееся в результате дерево рекурсии. После того как дерево построено, длительности выполнения всех его узлов суммируются по всем уровням. Полное время выполнения верхнего уровня равно сп, следующий уровень дает вклад, равный с(п/2) + с(п/2) = сп, общая стоимость уровня после него составляет с(п/4) + с(п/4) + с(п/4) + с(п/4) = сп, и т.д.

В общем случае уронены (если вести отсчет сверху) имеет 2' узлов, каждый из которых дает вклад в общее время работы алгоритма, равный с(п/2'), так что общая стоимосты-го уровня равна 2' с(п/2') = сп. На нижнем уровне имеется п узлов, каждый из которых дает вклад с, что в сумме также дает время, равное сп. Общее количество уровней дерева рекурсии на рис. 2.5 равно !я и + 1, где и— количество листьев, соответствующее размеру входных данных.

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

Для вычисления общей стоимости, представленной рекуррентным соотношением (2.2), нужно просто просуммировать вклацы от всех уровней. Всего имеется 1кп+ 1 уровней, каждый из которых имеет стоимость сп, так что полная стоимость составляет сп(!я п + 1) = сл 1я и + сп. Пренебрегая членом более низкого порядка и константой с, в результате получаем б!(и 1я и). Упражнения Используя в качестве образца рис. 2.4, проиллюстрируйте работу алгоритма сор- тировки слиянием для массива А = (3, 41, 52, 26, 38, 57, 9, 49) .

2.3.2 Перепишите процедуру Микол так, чтобы в ней не использовались сигнальные значения. Сигналом к остановке должен служить тот факт, что все элементы массива Ь или массива В скопированы обратно в массив А, после чего в этот массив копируются элементы, оставшиеся в непустом массиве. Часмь 1 Основы б2 Воспользуйтесь методом математической индукции для доказательства того, что, когда и является точной степенью 2, решением рекуррентного соотношения Т () 2 если п = 2, 2Т(п/2)+ п, если и = 2", к > 1, является Т(п) = п!яп.

2.3.4 Сортировку вставкой можно представить в виде рекурсивной последовательности. Чтобы отсортировать массив А[1., п[, сначала нужно рекурсивно отсортировать массив А[1 .. п — 1[, после чего в этот отсортированный массив помешается элемент А[п[. Запишите рекуррентное уравнение для времени работы этой рекурсивной версии сортировки вставкой. 2.3.5 Возвращаясь к задаче поиска (см. упр, 2.1.3), нетрудно заметить, что если последовательность А отсортирована, то можно сравнить значение среднего элемента этой последовательности с искомым значением е и сразу исключить половину последовательности из дальнейшего рассмотрения.

Бинарный ноиск !Ь!лагу зеагсЬ) — это алгоритм, в котором такая процедура повторяется неоднократно, что всякий раз приводит к уменьшению оставшейся части последовательности в два раза. Запишите псевдокод алгоритма бинарного поиска (либо итеративный, либо рекурсивный). Докажите, что время работы этого алгоритма в наихудшем случае составляет Й(!К п).

2.3.б Заметим, что в цикле эгЫ!е в строках 5-7 процедуры !мзнкт!о!ч-Конт в разделе 2.1 для сканирования (в обратном порядке) отсортированного подмассива А[1..3 — 1[ используется линейный поиск. Можно ли использовать бинарный поиск (см. упр, 2.3.5) вместо линейного, чтобы время работы этого алгоритма в наихудшем случае улучшилось и стало равным 9(п 1я п)? 2.3.~ * Разработайте алгоритм со временем работы б!(п!яп), который для заданного множества Я из п целых чисел и другого целого числа х определяет, имеются ли в множестве Я два элемента, сумма которых равна х. Задачи 2.1.

Сортировка вставкой малых массивов в нроцессе сортировки слиянием Несмотря на то что с увеличением количества сортируемых элементов время сортировки методом слияний в наихудшем случае растет как 9(п !кп), а время Глана 2. Приступаем к изучению бЗ сортировки вставкой — как Й(п ), благодаря постоянным множителям на практике для малых размеров задач на большинстве машин сортировка вставкой выполняется быстрее. Таким образом, есть смысл использовать сортировку вставок в процессе сортировки методом слияний, когда подзадачи становятся достаточно маленькими.

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

Если такой модифицированный алгоритм выполняется за время Е!(п)с + п !б(п/й)) в наихудшем случае, то чему равно наибольшее значение й как функции от и, для которого модифицированный алгоритм в ка-обозначениях имеет то же время работы, что и стандартная сортировка слиянием? * Как следует выбирать й на практике? 2.2. Корректность пузырьковой сортировки Пузырьковая сортировка представляет собой популярный, но не эффективный алгоритм сортировки.

В его основе лежит многократная перестановка соседних элементов, нарушающих порядок сортировки. ВувнййяОкт(А) ! хогг' = 1!о А.!епдгл — 1 2 аког з = А.1епдоз позгийо г+ 1 3 НА[Я < А[3 — Ц 4 поменять А[э] и А[д — 1] местами а Пусть А' обозначает выход процедуры Впввьпзокт(А). Для доказательства корректности процедуры ВпввьпзОкт необходимо доказать, что она завершается и что А'[1] < А'[2] « . - А'[и], (2.3) где и = А. !епдг6, Что еще необходимо доказать для того, чтобы показать, что процедура В1зввьпзокт действительно выполняет сортировку? В следующих двух частях доказываются неравенства (2.3).

б. Точно сформулируйте инвариант цикла аког в строках 2-4 и докажите, что он выполняется. Доказательство должно иметь ту же структуру доказательства инварианта цикла, которая ранее использовалась в аналогичных доказательствах в данной главе. Часть 2 Основы б4 в. С помощью условия завершения инварианта цикла, доказанного в части (б), сформулируйте инвариант цикла аког в строках 1-4, который позволил бы доказать неравенства (2.3). Доказательство должно иметь ту же структуру доказательства инварианта цикла, которая использовалась ранее в аналогичных доказательствах в данной главе.

* Определите время пузырьковой сортировки в наихудшем случае и сравните его со временем сортировки вставкой. 2.3. Корректность правила Горнера Следующий фрагмент кода реализует правило Горнера для вычисления поли- нома н Р(х) = ~~~ аьх к=о = ао + х(аз + х(аз + . + х(а„~ + ха„) )) для заданных коэффициентов ао, аы..., а„и значения х.

у=О 2 Гог г = и <$озгпйо 0 3 у=а +х у а Чему равно время работы этого фрагмента кода правила Горнера в б)-обозначениях? 6. Напишите псевдокод, реализующий алгоритм обычного вычисления поли- нома, когда каждое слагаемое полинома вычисляется отдельно. Определите асимптотическое время работы этого алгоритма и сравните его со временем работы алгоритма, основанного на правиле Горнера. ж Рассмотрим следующий инвариант цикла. В начале каждой итерации цикла 1ог в строках 2 и 3 н — (1.ь1) ь у = ~ аььг~-1х а=о Рассматривайте сумму без членов как равную нулю. Следуя структуре доказательства инварианта цикла, которая использовалась ранее в данной главе, воспользуйтесь указанным инвариантом цикла, чтобы показать, что по завершении работы у = 2 ь аьх~.