1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 24
Текст из файла (страница 24)
Понятно, что всякий элемент а„кроме а, обладает ключевым сравнением; иначе ие выполнилось бы ни а| !с+ра„, ни а И~ран Далее, легко видеть, что никакое сравнение не может быть ключевым для обоих сравниваемых элементов. Так как в ключевые сравнения должны вовлекаться и — 1 элементов, то длина пути р должна быть не меньше л — 1. С) Следствие. Нахождение й-го наименьшего элемента в 5 требует не меньше и — 1 сравнений как в среднем, так и в худшем случае.
На самом деле для всех й, кроме 1 и а, можно доказать более сильный результат, чем теорема 3.10. (См. упр. 3.21 — 3.23.) Если приходится искать алгоритм с хорошим средним временем, который вычисляет й-й наименыпий элемент в 5, то подходит стратегия типа той, что применялась в алгоритме Быстрсорт. Алгоритм 3.7. Нахождение й-го наименьшего элемента Вход.
Последовательность 5, состоящая из и элементов произвольного множества с линейным порядком (, и целое число й, 1(/г(п. Выход. й-й наименьший элемент в 5. Метод. Применяется рекурсивная процедура ВЫБОР, приведенная на рис. 3.12, С) Теорема 3.11. Среднее время работы алгоритма 3.7 линейно. 111 ГЛ. В. СОРТИРОВКА И ПОЛЯДКОВЪ|е СТАТИСТИКИ ргосейвге ВЫБОР(/г, 5): 1. В ~5'1=1 1Ьеп ге1вгп единственный элемент множества 5 е1зе Ьеи)п 2. случайно выбрать элемент а из 5; 3. пусть 5,, 5, и 5, †последовательнос элементов из 5, меньших, равных н больших а соответственно; 4.
11 15! ~) Ь 1Ьеп ге1пгп ВЫБОР(й, 5,) е1ве 6. 11 )51~+151~~)й 1Ьеп ге1вгп а 6, е(ве ге1вгп ВЫБОР(й — 15,! — 15,1, 5,) епд Рис. 3.12. Алгориты выбора. Д о к а з а т е л ь с т в о. Пусть Т (п) — среднее время работы процедуры ВЫБОР на последовательности из п элементов. Предположим для простоты, что все элементы множества 5 различны. (При наличии повторяющихся элементов результат не изменится.) Пусть элемент а, выбранный в строке 2, является 1-м наименьшим элементом в 5. Число ! может принимать значения 1, 2, ..., п равновероятно. Если !.
й, то ВЫБОР вызывается для последовательности, состоящей из ! — 1 элементов, а если !(Й, то для последовательности, состоящей из п — ! элементов. Поэтому среднее время работы рекурсии в строке 4 или 6 равно РА-1 л л-! л-! — '~',)',Т(п — !)+,'»', Т(! — 1)~= — „'~ ,'!' Т(1)+~Ч» Т(!) »= 1 »=АА1 ! л-А+! |=А Остальная часть процедуры ВЫБОР занимает время сп для некоторой постоянной с, так что при а~~2 л-! л-1 Т (п) (си+МАХ вЂ” ~~'„Т (1) + ~, Т (!) .
(3.9) ~г= -А+! ! А В качестве упражнения на индукцию предлагаем доказать, что если Т(1)<с, то Т(п)~Асп для всех п>2. П УПРАЖНЕНИЯ 3.1. Примените алгоритм 3.1 для упорядочения последовательности цепочек аЬс, асЬ, Ьса, ЬЬс, асс, Ьас, Ьаа. упиджнения Рис. ЗЛЗ. Два дерева. 3.2. Примените алгоритм 3.2 для упорядочения последовательности цепочек а, Ьс, ааЬ, Ьаса, сЬс, сс.
3.3. Проверьте, изоморфны ли два дерева на рис. 3,13 в смысле примера 3.2. 34. Упорядочите список 3,1,4,1,5,9,2,6,5,3,5,8,97, применяя (а) Сортдеревом, (б) Быстрсорт, (в) Сортслиянием (алгоритм 2.4). Сколько сравнений производится в каждом случаер 3.5. Рассмотрите следующий алгоритм, упорядочнвающнй последовательность элементов ао а„..., а„, хранящихся в массиве А, т. е. А[!)=а; для 1 !(и: ргоседпге СОРТВЗБАЛТЫВАНИЕМ(А): !ог !=и — 1 а!ер — 1 пп!!1 1 до !ог 1=1 а!ер 1 ппВ! ! бо 1! А [!+1! < А1!1 !)аеп переставить А((1и А !!+1! (а) Докажите, что СОРТВЗБАЛТЫВЛНИЕМ располагает элементы в А в порядке неубывания. (б) Определите время работы СОРТВЗБАЛТЫВАНИЕМ в худшем случае н в среднем.
3.6. Закончите доказательство того, что сортирующее дерево можно построить за линейное время (теорема 3.5). 3.7. Закончите доказательство того, что Сортдеревом требует время 0(и 1ой и) (теорема 3.6). 3.8. Покажите, что время работы Быстрсорт в худшем случае есть 0(а'). 3.9. Каково время работы в худшем случае у алгоритма 3.7, на.
ходящего Ь-й наименьший элементр гл. з. согтииовкх и погядковые стлтистики *3.10. Докажите, что среднее время упорядочения последовательности из и элементов ограничено снизу величиной си 1од и для некоторой постоянной с, закончив доказательство теоремы 3.7 н решив уравнение (3.2). 3.11. Закончите доказательство того, что алгоритм 3.6 находит й-й наименьший элемент за время 0(п) (теорема 3.9), решив уравнение (3.8). "3.12. Докажите корректность подпрограммы разбиения, приведенной на рис. 3.8, и проанализируйте время ее работы.
3.13. Закончите доказательство того, что алгоритм 3.7 для нахождения Ьго наименьшего элемента работает в среднем 0(л) времени (теорема 3.11), решив уравнение (3.9). *3.14. Покажите, что среднее число сравнений, требуемых алгоритмом 3.7, не превосходят 4п.Можете ли вы улучшить эту оценку, если известно значение й, прн котором будет применяться алгоритму *3.16. Пусть 5 — последовательность элементов, содержащая гл; экземпляров 1-го элемента для 1<1<8. Пусть а= ~ч , 'т~ Докажис=~ те, что 0(п+1од...
) сравнений необходимо н достаточно, чтобы упорядочить 5. 3.16. Пусть 5,, 5„..., 5 — множества чисел, лежащих между 1 н а, н сумма мощностей всех 5~ равна и. Опишите алгоритм сложности 0(и), упорядочивающнй все 5ь 3.17. Пусть даны последовательность ао ам..., а и перестановка и(1), п(2),..., п(а), Напишите алгоритм на Упрощенном Алголе, который располагал бы эту последовательность в порядке а „, а„„,,..., а„„„работая на том же месте, где она записана вначале. Каково время работы вашего алгоритма в худшем случае и в среднем? "3.18. В процессе построения сортнрующего дерева размера 2" — 1 мы строим два сортирующих дерева размера 2» ' — 1, затем соединяем их, добавляя корень и проталкивая элемент, стоящнй в корне, вниз на его надлежащее место. Столь же легко можно было бы построить сортирукицее дерево, добавляя за один шаг один элемент в качестве листа и проталкивая этот новый элемент вверх по дереву.
Напишите алгоритм, который строил бы сортирующее дерево с помощью добавления листа (одного на каждом шаге), и сравните порядок сложности вашего алгоритма и алгоритма 3.3. УПРАЖНЕНИЯ 3.19. Рассмотрим прямоугольный массив. Расположим элементы в каждой строке в порядке возрастания.
Затем расположим в порядке возрастания элементы каждого столбца. Докажите, что каждая строка останется упорядоченной. *3.20. ПуСтЬ ап В„..., ая — ПОСЛЕдОВатЕЛЬНОСтЬ ЭЛЕМЕНТОВ, а р и д — положительные целые числа. Рассмотрим подпоследовательности, образованные выбором каждого р-го элемента. Упорядочим их. Повторим этот процесс для д. Докажите, что подпоследовательности шага р останутся упорядоченными. **3.21. Рассмотрим нахождение с помощью сравнений наибольшего и второго по величине элемента в и-элементном множестве.
Докажите, что для этого необходимо и достаточно и+ ( 1од и 1 — 2 сравнений. **3.22. Покажите, что среднее число сравнений, требуемых для нахождения Ьго наименьшего элемента в и-элементной последовательности, не меньше (1+0,75 а(1 — а)) и, где а=А(п, а й и п достаточно велики.
"«3.23. Покажите, что в худшем случае требуется л+ +М1)Ч (й, п — А+1) — 2 сравнений для нахождения й-го наименьшего элемента в и-элементном множестве. "*3.24. Пусть 3 — множество, состоящее из п целых чисел. Допустим, что вы можете только складывать его элементы и сравнивать суммы. Сколько требуется сравнений для нахождения при этих условиях наибольшего элемента в 3? "3.25. Алгоритм 3.6 разбивает свой аргумент на подпоследовательностн размера 5. Будет ли этот алгоритм работать для других размеров, например 3, 7 или 9? Выберите тот размер, который минимизирует общее число сравнений.
На рис. 3.14 указано наименьшее известное число сравнений, достаточное для упорядочения множеств различных размеров. Известно, что для п(12 эти числа оптимальны. Я3.26. Алгоритм 3.5 разбивает данную последовательность на подпоследовательности длины 5, а затем находит медиану медиан. Вместо того, чтобы искать медиану медиан, не будет ли эффективнее найти какой-нибудь другой элемент, например ( й/5 ~ -йР Размер и часаа араваеааа" Рис.
ЗЛ4. Число сравнений, достаточное для упорядочения последовательности из и злеиеитов (наныеныние известные значеиив). ГЛ. К СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ *3.27. Рассмотрим следующий метод сортировки. Начнем с последовательности, состоящей из одного элемента. В эту последовательность по одному будем вставлять другие элементы с помощью двоичного поиска. Придумайте структуру данных, позволяющую быстро производить двоичный поиск и вставлять элементы.
Можете ли вы реализовать эту сортировку за время 0(н )од п)7 ""3.28. Вместо того, чтобы для разбиения множества размера и выбирать произвольный элемент, как мы делали в Быстрсорт нли алгоритме 3.7, можно было бы сделать небольшую выборку, скажем, размера з, найти ее медиану и использовать ее, чтобы разбить все множество. Укажите, как надо выбрать з как функцию от н, чтобы минимизировать среднее число сравнений, необходимых для сортировки. *е3.29.
Обобщите идею упр. 3.28 так, чтобы минимизировать число сравнений, необходимых для нахождения порядковой статистики. Указание: Извлеките из выборки два элемента, между которыми с большой вероятностью лежит искомый элемент. 3.30. Метод сортировки стабилен, если равные элементыостаются в упорядоченной последовательности в том жеотносительном порядке, в каком они были в исходной последовательности. Какой из перечисленных ниже алгоритмов стабиленР (а) СОРТВЗБАЛТЫВАНИЕМ (упр. 3.5) (б) Сортслиянием (алгоритм 2.4) (в) Сортдеревом (алгоритм 3.4) (г) Быстрсорт (алгоритм 3.5) Проблема для исследования 3,31. Некоторые проблемы, касающиеся числа сравнений, не.
обходимых в определенных ситуациях, все еще не решены. Например, пусть требуется найти я наименьших элементов из л-элементного множества. Случай й=З рассмотрен Праттом, Яо П973). Для и'-в13 неизвестно, оптимальны ли для упорядочения и элементов числа, приведенные в таблице на рис. 3.14. Для малых п оптимальным в смысле числа сравнений является алгоритм сортировки из работы Форда, Джонсона [1959) '). ') Отметим, что окончательное решение эадачи о порядке сложности сортировки не получено, а именно не известны ответы на некоторые естественные во.
просы, Например, рассмотрим сортировку л натуральных чисел, каждое иэ которых имеет длину двоичного представления й, на адресной машине с длиной регистров! (й и ( — функции от л). Если сортируемые числа подаются на .вход поразрядно, то время считывания входных данных (т. е. тривиальная нижняя оценка сложности) есть йп; алгоритмы такой сложности наложены в гл. 3. Пусть теперь сортируемые числа считываются частями длины 5 т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
