Как решить это рекуррентное соотношение: T (n) = 4 * T (sqrt (n)) + n

Я знаю, как решить рекуррентные отношения с помощью Master Method. Также я'Я знаю, как решить повторения ниже:

T (n) = sqrt (n) * T (sqrt (n)) + n

T (n) = 2 * T (sqrt (n)) + lg (n)

В приведенных выше двух рекурсиях на каждом уровне дерева рекурсии выполняется одинаковый объем работы. И есть всего log log n уровней в дереве рекурсии.

У меня возникли проблемы в решении этого: T (n) = 4 * T (sqrt (n)) + n

РЕДАКТИРОВАТЬ: Здесь n - степень 2

 beta0x6419 нояб. 2012 г., 17:55
Я думаю, что это относится к теоретическому сайту обмена стека CS
 Brett Hale01 мар. 2016 г., 04:31
Я голосую, чтобы закрыть этот вопрос как не по теме, потому что он принадлежитматематика, Или один из сайтов CS.
 Abhinav Gupta19 нояб. 2012 г., 18:13
Я поступил так же, как предложили вы.
 Abhinav Gupta19 нояб. 2012 г., 18:12
У меня есть образец, но я не могу его решить ... !!
 beta0x6419 нояб. 2012 г., 17:56
В любом случае вы просто держитеразгадка» рекуррентное соотношение путем подстановки исходного уравнения обратно для T () и распределения. Вы делаете это до тех пор, пока не наблюдаете шаблон, а затем определяете этот шаблон обычно в терминахк «.

Ответы на вопрос(3)

   T(n) = 4 T(sqrt(n)) + n
   4 [ 4 T(sqrt(sqrt(n) + n ] + n
   4^k * T(n^(1/2^k)) +kn because n is power of 2.
   4^k * T(2^(L/2^k)) +kn   [  Let n = 2^L , L= logn]
   4^k * T(2) +kn   [  Let L = 2^k,  k = logL = log log n]
   2^2k * c +kn
   L^2 * c + nloglogn 
   logn^2 * c + nloglogn
   = O(nloglogn)

РЕДАКТИРОВАТЬ: Здесь п это степень 2

Это редактирование важно. Итак, допустим, что повторение останавливается на 2.

Итак, вопрос сейчас в том, насколько глубоко дерево рекурсии. Ну вот, сколько раз вы можете получить квадратный корень из n, прежде чем n станет достаточно маленьким (скажем, меньше 2). Если мы напишем

п = 2LG N

тогда при каждом рекурсивном вызове n будет взят его квадратный корень. Это эквивалентно вдвое меньшему показателю, поэтому после k итераций имеем

1 / (2k) = 2LG N / (2 КБ)

Мы хотим остановиться, когда это меньше 2, давая 2

LG N / (2 КБ) = 2

LG н / (2к) = 1

lg n = 2k

LG LG N = K

Таким образом, после lg lg n итераций квадратного корня рекурсия останавливается. (источник)

Для каждой рекурсии у нас будет 4 новых ветви, поэтому общее количество ветвей равно 4 ^ (глубина дерева).4^(lg lg n)

РЕДАКТИРОВАТЬ:

Источник

 dreamcrash21 нояб. 2012 г., 01:02
T (n) = 4 * T (sqrt (n)) + n. У вас также есть «н» кроме sqrt (n)
 fgb21 нояб. 2012 г., 01:30
Каждый уровень имеет свое значение для n, хотя на втором уровне у вас больше нет + n, но есть + sqrt (n).
 dreamcrash21 нояб. 2012 г., 17:25
@fgb Вы правы, я только что исправил.
 Yu-Han Lyu20 нояб. 2012 г., 23:55
Почему каждый уровень рекурсии работает O (n)? Рассмотрим второй уровень. Поскольку существует 4 ветви и каждая ветвь T (sqrt (n)), работа должна быть 4 sqrt (n) на втором уровне.

что n = 2 ^ k. Мы имеем T (2 ^ k) = 4 * T (2 ^ (k / 2)) + 2 ^ k. Пусть S (k) = T (2 ^ k). Мы имеем S (k) = 4S (k / 2) + 2 ^ k. Используя теорему Матера, получаем S (k) = O (2 ^ k). Поскольку S (k) = O (2 ^ k) и S (k) = T (2 ^ k), T (2 ^ k) = O (2 ^ k), что влечет T (n) = O (n).

 dreamcrash21 нояб. 2012 г., 17:27
+1, да это правильно.
 rasen5806 сент. 2017 г., 17:05
Можете ли вы действительно использовать Основную теорему здесь, хотя, так как 2 внутри S (k / 2) не является постоянной в этом случае? I '

Ваш ответ на вопрос