решение T(n) = 2T(n/2) + log n [закрыто]

Закрыто. Этот вопрос не по теме. В настоящее время ответы на него не принимаются.

Хотите улучшить этот вопрос? Обновите вопрос, чтобы он был по теме для Stack Overflow.

Закрыт 8 лет назад.

Я пытаюсь решить T(n) = 2T(n/2) + log n

подставил n = 2^k

T(2^k) = 2T(2^(k-1)) + k  
T(2^k) = 2^2 T(2^(k-1)) + 2(k-1) + k

after k steps
T(2^k) = 2^k T(1) + 2^(k-1) + 2 * (2^(k-2)) +....+k

То есть по сути мне нужно просуммировать член i*2^i где i = 1 до log n - 1.
И я не смог найти простой способ суммировать эти члены. Может я делаю что-то не так? Есть ли другой способ решить эту рекурсию? Сработает ли теорема Мастера? Если да, то как?

Спасибо.

divide-and-conquer recurrence

задан Rohit chauhan 29 September 2011 в 05:42

0 ответов

Другие вопросы по тегам:

divide-and-conquer recurrence

решение T(n) = 2T(n/2) + log n [закрыто]

0 ответов

Похожие вопросы: