А. Шень ðòïçòáííéòï÷áîéå ÔÅÏÒÅÍÙ É ÚÁÄÁÞÉ Издание седьмое, дополненное Москва



Pdf көрінісі
бет3/9
Дата04.11.2023
өлшемі1,66 Mb.
#122042
түріКнига
1   2   3   4   5   6   7   8   9
Байланысты:
теория


Разделение элементов сортируемого участка на три категории (мень-
шие, равные, больше) рассматривалась в главе
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   2   3   4   5   6   7   8   9




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет