Рекуррентность W (n) = 2W (этаж (n / 2)) + 3

Question

У меня есть такое повторение:

W(n)= 2W(floor(n/2)) + 3
W(2)=2

Моя попытка заключается в следующем:

дерево выглядит так:

W(n) = 2W(floor(n/2)) + 3
W(n/2) = 2W(floor(n/4)) + 3
W(n/4) = 2W(floor(n/8)) + 3 
...

• высотадерево: я предполагаю его lgn, потому что дерево имеет 2 ветви на каждом процессе расширения, хотя не уверен: S
• стоимость последнего уровня: 2 ^ lgn * W (2) = 2n
• стоимость всех уровней до уровня h-1: 3 * сигма от 0 до lgn-1 of (2 ^ i), которая представляет собой геометрический ряд = 3 (n-1)

Итак, T (n) = 5n - 3, которые принадлежат Theta (n)

. Мой вопрос: так ли это?

Answer 1

Я не думаю, что это точно 5n-3, за исключением того, что n равно 2 ^t , но ваша тэта верна, если вы посмотрите на Основная теорема , нет необходимости вычислять ее (но это хорошо для запуска):

предположим, что у вас есть:

T (n) = aT (n / b) + f (n), где a> = 1, b> 1, затем:

1. если f (n) = n ^{log _b a-eps} для любого eps> 0, то T (n) = n ^{log _b a} как ваш случай, в котором a = b = 2, f (n) = O (1).
2. f (n) = Theta (n ^{log _b a} * log ^k n), затем T (n) = Theta (n ^{log _b a} * log ^{k + 1} n).
3. В противном случае это тэта (f (n)). (см. подробности ограничения в этом случае в CLRS или вики, ...)

Подробнее см. Вики.

Answer 2

Ну, если вы подсчитаете W(4), вы найдете W(4) = 2*W(2) + 3 = 2*2 + 3 = 7, но 5*4 - 3 = 17, поэтому ваш результат для T(n) неверен. Это близко, хотя, есть только незначительная ошибка в ваших рассуждениях (или, возможно, в каком-то другом месте).

Изменить: Если быть точным, ваш расчет сработает, если будет дано W(1), но в вопросе указано W(2). Либо последний опечатка, или вы один на один с ростом. (и, конечно, то, что сказал Саид Амири.)