Я хотел бы решить следующее рекуррентное соотношение:повторения Т (п) = 2T (SQRT (N))
Т (п) = 2T (√ п);
Я предполагаю, что T(n) = O(log log n), но я не уверен, как это доказать. Как бы я показал, что этот рецидив решает O(log log n)?
Одной из идей было бы упростить повторение, введя новую переменную k такую, что 2 k = n. Тогда рекуррентное соотношение работает в
T (2 к) = 2T (2 к/2)
Если то пусть S (к) = T (2 К), вы получите рекуррентное
S (к) = 2S (к/2)
Обратите внимание, что это эквивалентно
S (K) = 2S (K/2) + O (1)
С 0 = О (1). Поэтому по Мастер-теореме получаем, что S (k) = Θ (k), так как мы имеем, что a = 2, b = 2 и d = 0 и log b a> d.
Так как S (к) = Θ (к) и S (к) = Т (2 к) = Т (п), получаем, что Т (п) = Θ (к). Поскольку мы выбрали 2 k = n, это означает, что k = log n, поэтому T (n) = Θ (log n). Это означает, что ваше первоначальное предположение O (log log n) неверно и что время выполнения является только логарифмическим, а не дважды логарифмическим. Если бы был сделан только один рекурсивный вызов, вы были бы правы, что время выполнения было бы O (log log n).
Надеюсь, это поможет!
Как получилось S (k) = T (2^k)? домен не совпадает, не должно ли оно быть S (k ') = T (2^k)? – Ritwik
Можете ли вы рассказать о том, что вы имеете в виду о доменах, которые не советуют? Я не понимаю, о чем вы спрашиваете. – templatetypedef
Я имел в виду, как вы можете подставить S (k) для T (2^k)? Если рассматривать их как функции от k и 2^k, то область T равна 1,2,4,8, ... И S равно 1,2,3,4, ... – Ritwik
Вы можете решить эту проблему легко разворачивая рекурсии:
Теперь повторение завершится, когда T(1) = a и вы можете найти подходящий a. Когда a = 0 или 1 это не имеет смысла, но когда a=2 вы получите:
Подставив k в последней части первого уравнения вы получите сложность O(log(n)).
Проверить другие аналогичные рекурсии здесь:
@AaronMcDaid, что будет "функция T одного параметра применяется к числу п". Специальной «T-нотации» нет. –
@ n.m., Я не помню, чтобы когда-либо в этой теме. Почему вы ответили мне на этот вопрос? Вы сами? –
@AaronMcDaid был у вас вопрос или кто-то с именем пользователя, похожим на ваш, спрашивая о «T (n) нотации». Теперь он удален. Опечатка возможна (я набирал ник вручную), но маловероятно, и сколько подобных именных имен для начала? –