Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[61]

Рис. 10.1 Анализ алгоритма select. Элементы массива (их п) изображены кружками, каждый столбец - группа из 5 или меньше элементов, белые кружки - медианы групп. «Медиана медиан» обозначена буквой х. Стрелки идут от больших чисел к меньшим. Видно, что в каждом из полных столбцов правее х имеется три числа, больших х, и что в каждом из столбцов левее х имеется три числа, меньших х. Множество чисел, заведомо больших х, выделено серым.

Пусть теперь Т{п) - время работы алгоритма Select на массиве из га элементов в худшем случае. Первый, второй и четвертый шаги выполняются за время О (га) (на втором шаге мы О (га) раз сортируем массивы размером 0(1)), третий шаг выполняется за время не более Т([га/5]), а пятый шаг, по доказанному, - за время, не превосходящее Т([7га/10 + 6]) (как и раньше, можно предполагать, что Т(п) монотонно возрастает с ростом га). Стало быть,

Т(га) Т(\п/5]) + Т([7га/10 + 6J) + 0(п).

Поскольку сумма коэффициентов при га в правой части (1/5 + 7/10 = 9/10) меньше единицы, из этого рекуррентного соотношения вытекает, что Т{п) era для некоторой константы с. Это можно доказать по индукции. В самом деле, предполагая, что T(m) сто для всех то < га, имеем

Т(га) с(\п/5]) + с([7га/10 + 6j) + 0(п) с(п/5 + 1) + с(7га/10 + 6) + 0(п) 9сга/10 + 7с+О(га) = = сп - с(га/10 - 7) + 0(п).

При подходящем выборе с это выражение будет не больше сп при всех га > 70 (надо, чтобы с(га/10 - 6) превосходило коэффициент, подразумеваемый в О(п)). Таким образом, индуктивный переход возможен при га > 70 (заметим ещё, что при таких га выражения [га/5] и [7га/10 + 6] меньше га).

Увеличив с ещё (если надо), можно добиться того, чтобы Т{п) не превосходило era и при всех га 70, что завершает рассуждение по индукции. Стало быть, алгоритм Select работает за линейное время (в худшем случае).


Отметим, что алгоритмы Select и Randomized-Select, в отличие от описанных в главе 9 алгоритмов сортировки за линейное время, используют только попарные сравнения элементов массива и применимы для произвольного упорядоченного множества. Эти алгоритмы асимптотически эффективнее очевидного подхода «упорядочи множество и выбери нужный элемент», поскольку всякий алгоритм сортировки, использующий только попарные сравнения, требует времени fi(ralgra) не только в худшем случае (раздел 9.1), но и в среднем (задача 9-1).

Упражнения

10.3-1 Будет ли алгоритм Select работать за линейное время, если разбивать массив на группы не из пяти, а из семи элементов? Покажите, что для групп из трёх элементов рассуждение не проходит.

10.3-2 Пусть х - «медиана медиан» в алгоритме Select (массив содержит га элементов). Покажите, что при га 38 количество элементов, больших х (так же как и количество элементов, меньших х) не меньше [~га/4].

10.3-3 Модифицируйте алгоритм быстрой сортировки так, чтобы он работал за время О (га lgra) в худшем случае.

10.3-4* Пусть алгоритм выбора г-го по счёту элемента использует только попарные сравнения. Покажите, что с помощью тех же сравнений можно в качестве побочного результата получить списки элементов, меньших искомого, а также больших искомого.

10.3-5 Пусть у нас есть какой-то алгоритм, находящий медиану за линейное в худшем случае время. Используя его в качестве подпрограммы, разработайте простой алгоритм, решающий задачу нахождения произвольной порядковой статистики за линейное время.

10.3-6 Под /г-квантилями (A;-th quantiles) множества из га чисел мы понимаем к - 1 его элементов, обладающих следующим свойством: если расположить элементы множества в порядке возрастания, то квантили будут разбивать множество на к равных (точнее, отличающихся не более чем на один элемент) частей. Разработайте алгоритм, который за время O(ralgfc) находит /г-квантили данного множества.

10.3-7 Разработайте алгоритм, который по заданному к находит в данном множестве S его к элементов, менее всего отстоящих от медианы. Число операций должно быть 0(15*1).


Рис. 10.2 Как провести с востока на запад магистраль, чтобы суммарная длина подводящих трубопроводов была минимальна?

10.3-8 Пусть Х[1..га] и У[1..га] - два возрастающих массива. Разработайте алгоритм, находящий за время O(lgra) медиану множества, полученного объединением элементов этих массивов.

10.3-9 Профессор консультирует нефтяную компанию, которой требуется провести магистральный нефтепровод в направлении строго с запада на восток через нефтеносное поле, на котором расположены га нефтяных скважин. От каждой скважины необходимо подвести к магистрали трубопровод по кратчайшему пути (строго на север или на юг, рис. 10.2). Координаты всех скважин профессору известны; необходимо выбрать местоположение магистрали, чтобы сумма длин всех трубопроводов, ведущих от скважин к магистрали, была минимальна. Покажите, что оптимальное место для магистрали можно найти за линейное время.

Задачи

10-1 Сортировка г наибольших элементов

Дано множество из га чисел; требуется выбрать из них г наибольших и отсортировать (пользуясь только попарными сравнениями). Для каждого из приведенных ниже подходов разработайте соответствующий алгоритм и выясните, как зависит от га и г время работы этих алгоритмов в худшем случае.

а.Отсортировать все числа и выписать г наибольших.

б.Поместить числа в очередь с приоритетами и вызвать г раз процедуру Extract-Max.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]