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


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




[17]

i log4 га. Заметив, что ra/48J га/4г, мы можем оценить наш ряд убывающей геометрической прогрессией (плюс последний член, соответствующий 3log4n задачам ограниченного размера):

Т(п) га + Зга/4 + 9га/16 + 27га/64 + ... + 3log4 пв(1)

со , . i

raEu +0(ralog43)

8 = 0 7

= 4га + о(га) = 0(п)

(Мы заменили конечную сумму из не более чем log4 га + 1 членов на сумму бесконечного ряда, а также переписали 3log411 как ralog43, что есть о(га), так как log4 3 < 1.)

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

Особенно много хлопот доставляют округления (переход к целой части). Для начала стоит предположить, что значения параметра таковы, что округления не требуются (в нашем примере при га = 4к ничего округлять не придётся). Вообще говоря, такое предположение не вполне законно, так как оценку надо доказать для всех достаточно больших целых чисел, а не только для степеней четвёрки. Мы увидим в разделе 4.3, как можно обойти эту трудность (см. также задачу 4-5).

Деревья рекурсии

Процесс подстановки соотношения в себя можно изобразить в виде дерева рекурсии (recursion tree). Как это делается, показано на рис. 4.1 на примере соотношения

Г(га) = 2Г(га/2) + га2.

Для удобства предположим, что га - степень двойки. Двигаясь от (а) к (г), мы постепенно разворачиваем выражение для Т(п), используя выражения для Т(п), Г(га/2), Г(га/4) и т.д. Теперь мы можем вычислить Т(п), складывая значения вершин на каждом уровне. На верхнем уровне получаем га2, на втором - (п/2)2 + (п/2)2 = га2/2, на третьем - (га/4)2 + (га/4)2 + (га/4)2 + (га/4)2 = га2/4. Получается убывающая геометрическая прогрессия, сумма которой отличается от её первого члена не более чем на постоянный множитель. Итак, Т(п) = ©(га2).

На рис. 4.2 показан более сложный пример - дерево для соотношения

Т(п) = Г(га/3) + Г(2га/3) + га


Рис. 4.1 Дерево рекурсии для соотношения Т(п) = 2Т(п/2) + п2. Высота полностью развернутого дерева (г) равна lg п (дерево имеет lg п + 1 уровней).

Рис. 4.2 Дерево рекурсии для соотношения Т(п) = Т(п/3) + Т(2п/3) + п.

Total=Bcero


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

(при таком к мы имеем (2/3)fcra = 1). Поэтому Г( га) можно оценить как O(ralgra).

Упражнения

4.2-1 Итерируя (подставляя в себя) соотношение Т(п) = ЗТ( га/2 ) + га, найдите хорошую верхнюю асимптотическую оценку для Т(п).

4.2-2 Анализируя дерево рекурсии, покажите, что Т(п) = Т(га/3) + Т(2га/3) + га влечёт Т(п) = fi(ralgra).

4.2-3 Нарисуйте дерево рекурсии для Т(п) = 4Т( га/2 ) + га и получите асимптотически точные оценки для Т(п).

4.2-4 С помощью итераций решите соотношение Т(п) = Т(п - а) + Т(а) + п, где а 1 - некоторая константа.

4.2-5 С помощью дерева рекурсии решите соотношение Т(п) = Т(ап) + Г((1 - а)п) + га, где а - константа в интервале 0 < а < 1.

Этот метод годится для рекуррентных соотношений вида

где а ) 1 и ft > 1 - некоторые константы, а / - положительная (по крайней мере для больших значений аргумента) функция. Он даёт общую формулу; запомнив её, можно решать в уме различные рекуррентные соотношения.

Соотношение (4.5) возникает, если алгоритм разбивает задачу размера га на а подзадач размера га/6, эти подзадачи решаются рекурсивно (каждая за время Т(п/Ъ)) и результаты объединяются. При этом затраты на разбиение и объединение описываются функцией /(га) (в обозначениях раздела 1.3.2 /(га) = С(п) + D(n)). Например, для процедуры Merge-Sort мы имеем а = 2, 6 = 2,

Как всегда, в формуле (4.5) возникает проблема с округлением: га/6 может не быть целым. Формально следовало бы заменить

4.3. Общий рецепт

(4.5)

/(га) = 0(га).



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