А. Шень ðòïçòáííéòï÷áîéå ÔÅÏÒÅÍÙ É ÚÁÄÁÞÉ Издание седьмое, дополненное Москва
жүктеу/скачать 1,66 Mb. Pdf көрінісі
|
Разделение элементов сортируемого участка на три категории (мень- шие, равные, больше) рассматривалась в главе 1 , с. 36 (это можно сде- лать за время, пропорциональное длине участка). Конечность глубины рекурсии гарантируется тем, что длина сортируемого участка на ка- ждом уровне рекурсии уменьшается хотя бы на 1. 7.4.8. (Для знакомых с основами теории вероятностей). Докажите, что математическое ожидание числа операций при работе этого ал- 7.4. Другие применения рекурсии 133 горитма не превосходит 𝐶𝑛 log 𝑛, причём константа 𝐶 не зависит от сортируемого массива. [Указание. Пусть 𝑇 (𝑛) | максимум математического ожидания чи- сла операций для всех входов длины 𝑛. Из текста процедуры вытекает такое неравенство: 𝑇 (𝑛) 6 𝐶𝑛 + 1 𝑛 ∑︁ 𝑘+𝑙=𝑛 − 1 (︀ 𝑇 (𝑘) + 𝑇 (𝑙) )︀ Первый член соответствует распределению элементов на меньшие, рав- ные и большие. Второй член | это среднее математическое ожидание для всех вариантов случайного выбора. (Строго говоря, поскольку сре- ди элементов могут быть равные, в правой части вместо 𝑇 (𝑘) и 𝑇 (𝑙) должны стоять максимумы 𝑇 (𝑥) по всем 𝑥, не превосходящим 𝑘 или 𝑙, но это не мешает дальнейшим рассуждениям.) Далее индукцией по 𝑛 нуж- но доказывать оценку 𝑇 (𝑛) 6 𝐶 ′ 𝑛 ln 𝑛. При этом для вычисления средне- го значения 𝑥 ln 𝑥 по всем 𝑥 = 1, . . . , 𝑛 − 1 нужно вычислять ∫︀ 𝑛 1 𝑥 ln 𝑥 𝑑𝑥 по частям как ∫︀ ln 𝑥 𝑑(𝑥 2 ). При достаточно большом 𝐶 ′ член 𝐶𝑛 в пра- вой части перевешивается за счёт интеграла ∫︀ 𝑥 2 𝑑 ln 𝑥, и индуктивный шаг проходит.] 7.4.9. Имеется массив из 𝑛 различных целых чисел и число 𝑘. Требу- ется найти 𝑘-е по величине число в этом массиве, сделав не более 𝐶𝑛 дей- ствий, где 𝐶 | некоторая константа, не зависящая от 𝑘 и 𝑛. Замечание. Сортировка позволяет очевидным образом сделать это за 𝐶𝑛 log 𝑛 действий. Очевидный способ: найти наименьший элемент, затем найти второй, затем третий, . . . , 𝑘-й требует порядка 𝑘𝑛 дей- ствий, то есть не годится (константа при 𝑛 зависит от 𝑘). [Указание. Изящный (хотя практически и бесполезный | константы слишком велики) способ сделать это таков: А. Разобьём наш массив на 𝑛/5 групп, в каждой из которых по 5 эле- ментов. Каждую группу упорядочим. Б. Рассмотрим средние элементы всех групп и перепишем их в мас- сив из 𝑛/5 элементов. С помощью рекурсивного вызова найдём средний по величине элемент этого массива. В. Сравним этот элемент со всеми элементами исходного массива: они разделятся на большие его и меньшие его (и один равный ему). Подсчитав количество тех и других, мы узнаем, в какой из этих частей должен находится искомый (𝑘-й) элемент и каков он там по порядку. Г. Применим рекурсивно наш алгоритм к выбранной части. 134 7. Рекурсия Пусть 𝑇 (𝑛) | максимально возможное число действий, если этот способ применять к массивам из не более чем 𝑛 элементов (𝑘 может быть каким угодно). Имеем оценку: 𝑇 (𝑛) 6 𝐶𝑛 + 𝑇 (𝑛/5) + 𝑇 (примерно 0,7𝑛). Последнее слагаемое объясняется так: при разбиении на части каждая жүктеу/скачать 1,66 Mb. Достарыңызбен бөлісу:
|