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


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




[5]

sorted sequence - отсортированная последовательность merge - слияние

initial sequence - начальная последовательность

Рис. 1.3 Сортировка слиянием для массива А = (5, 2, 4, 6, 1, 3, 2, 6).

Весь массив теперь можно отсортировать с помощью вызова Merge-Sort(A, 1, length[A]). Если длина массива га = length[A] есть степень двойки, то в процессе сортировки произойдёт слияние пар элементов в отсортированные участки длины 2, затем слияние пар таких участков в отсортированные участки длины 4 и так далее до га (на последнем шаге соединяются два отсортированных участка длины га/2). Этот процесс показан на рис. 1.3.

1.3.2. Анализ алгоритмов типа «разделяй и властвуй»

Как оценить время работы рекурсивного алгоритма? При подсчёте мы должны учесть время, затрачиваемое на рекурсивные вызовы, так что получается некоторое рекуррентное соотношение (recurrence equation). Далее следует оценить время работы, исходя из этого соотношения.

Вот примерно как это делается. Предположим, что алгоритм разбивает задачу размера га на а подзадач, каждая из которых имеет в Ь раз меньший размер. Будем считать, что разбиение требует времени D(n), а соединение полученных решений - времени С(га).


Тогда получаем соотношение для времени работы Т{п) на задачах размера га (в худшем случае): Т{п) = аТ(п/Ь) + D(n) + С(га). Это соотношение выполнено для достаточно больших га, когда задачу имеет смысл разбивать на подзадачи. Для малых га, когда такое разбиение невозможно или не нужно, применяется какой-то прямой метод решения задачи. Поскольку га ограничено, время работы тоже не превосходит некоторой константы.

Анализ сортировки слиянием

Для простоты будем предполагать, что размер массива (га) есть степень двойки. (Как мы увидим в главе 4, это не очень существенно.) Тогда на каждом шаге сортируемый участок делится на две равные половины. Разбиение на части (вычисление границы) требует времени ©(1), а слияние - времени О(га). Получаем соотношение

Как мы увидим в главе 4, это соотношение влечёт Т{п) = в (га log га), где через log мы обозначаем двоичный логарифм (основание логарифмов, впрочем, не играет роли, так как приводит лишь к изменению константы). Поэтому для больших га сортировка слиянием эффективнее сортировки вставками, требующей времени 0(га2).

Упражнения

1.3-1 Следуя образцу рис. 1.3, показать работу сортировки слиянием для массива А = (3, 41, 52, 26, 38, 57, 9,49).

1.3-2 Написать текст процедуры Merge (А, р, q, г).

1.3-3 Докажите по индукции, что если

то Т(п) = га log га (при всех га, являющихся степенями двойки).

1.3-4 Сортировку вставками можно оформить как рекурсивную процедуру: желая отсортировать А[1. .га], мы (рекурсивно) сортируем А[1. .га - 1], а затем ставим А[п] на правильное место в отсортированном массиве А[1. .га - 1]. Напишите рекуррентное соотношение для времени работы такой процедуры.

если га = 1

2,если га = 2,


1.3-5 Возвращаясь к задаче поиска (упр. 1.1-3), заметим, что при поиске в отсортированном массиве мы можем сначала сравнить искомый элемент со средним элементом массива, узнать, в какой половине его следует искать, а затем применить ту же идею рекурсивно. Такой способ называется двоичным поиском (binary search). Напишите соответствующую программу, используя цикл или рекурсию. Объясните, почему время её работы есть О (log га).

1.3-6 Заметим, что цикл while в строках 5-7 процедуры Insertion-Sort (разд. 1.1) просматривает элементы отсортированного участка А[1. .j - 1] подряд. Вместо этого можно было бы использовать двоичный поиск (упр. 1.3-5), чтобы найти место вставки за время О (log га). Удастся ли таким образом сделать общее время работы равным ©(га log га)?

1.3-7* Дан массив S из га действительных чисел, а также число х. Как за время ©(ralogra) определить, можно ли представить х в виде суммы двух элементов массива S?

Замечания

Как мог бы сказать Козьма Прутков, хороший алгоритм подобен острому ножу - тот и другой достигают цели легко и просто. Другое сравнение: человек, пользующийся плохим алгоритмом, подобен повару, отбивающему мясо отвёрткой: едва съедобный и малопривлекательный результат достигается ценой больших усилий.

Часто разница между плохим и хорошим алгоритмом более существенна, чем между быстрым и медленным компьютером. Пусть мы хотим отсортировать массив из миллиона чисел. Что быстрее - сортировать его вставками на суперкомпьютере (100 миллионов операций в секунду) или слиянием на домашнем компьютере (1 миллион операций)? Пусть к тому же сортировка вставками написана на ассемблере чрезвычайно экономно, и для сортировки га чисел нужно, скажем, лишь 2га2 операций. В то же время алгоритм слиянием написан без особой заботы об эффективности и число операций есть 50га log га. Для сортировки миллиона чисел получаем

10 операций в секунду для домашнего компьютера.

Мы видим, что разработка эффективных алгоритмов - не менее важная компьютерная технология, чем разработка быстрой электроники. В этой области также происходит заметный прогресс.

20 000 секунд рй 5,56 часов

10 операций в секунду для суперкомпьютера и всего

операции

1 000 секунд рй 17 минут



[стр.Начало] [стр.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]