Это захватывающее повторение, и оно не решает to (n). Скорее, он решает Θ (n 2/3 ) .
Чтобы дать интуицию, почему это вряд ли будет Θ (n) давайте представим, что мы имеем дело с действительно, очень большим значением n. Тогда, поскольку
T (n) = (nT (√n) + n) 1/2
при условии, что T (√ n) ≈ √n, мы получили бы, что
T (n) = (n√n + n) 1/2
= (n 3/2 + n) 1/2
≈ n 3/4 .
В других слова, предполагая, что T (n) = Θ (n) даст нам другое значение T (n), так как n становится большим.
С другой стороны, давайте предположим, что T (n) = Θ ( п * * 2 тысяча тридцать семь / 3 ). Тогда тот же расчет дает нам, что
T (n) = (nT (n) + n) 1/2
= (n · n 2/3 + n) 1/2
≈ (n 4/3 ) 1/2
= n 2/3 ,
, что соответствует самому себе.
Чтобы проверить это, я написал короткую программу, которая распечатывала разные Значения T (n) приведены с разными входами и нанесены на график результатов. Вот версия T (n), которую я написал:
double T(double n) {
if (n <= 2) return n;
return sqrt(n * T(sqrt(n)) + n);
}
Я решил использовать 2 в качестве базового случая, так как многократное получение квадратных корней никогда не позволит n упасть до одного. Я также решил использовать вещественные аргументы, а не дискретные целочисленные значения просто для упрощения математики.
Если вы построите значения T (n), вы получите эту кривую:
.
Это не похоже на то, что я ожидаю от линейного графика. Чтобы выяснить, что это было, я нанёс это на график log / log, который обладает прекрасным свойством, заключающимся в том, что все полиномиальные функции преобразуются в прямые линии, наклон которых равен показателю степени. Вот результат:
Я обратился к своему программному обеспечению для регрессии Handy Neighborhood и попросил его определить наклон этой линии. Вот что оно вернуло:
Наклон: 0,653170918815869
R 2 : 0,9999942627574643
Это очень хорошо подходит, а уклон 0,653 довольно близок к 2/3. Так что это более эмпирическое доказательство, подтверждающее, что рецидив решается до Θ (n 2/3 ).
Все, что осталось сделать сейчас, это выработать математику. Мы решим это повторение, используя серию подстановок.
Во-первых, мне, как правило, не очень удобно работать с показателями так, как это повторение использует, поэтому давайте возьмем журнал обеих сторон. (На протяжении всей этой статьи я буду использовать lg n для обозначения log 2 n).
lg T (n) = lg (nT (√n) + n) 1/2
= (1/2) lg (nT (√n) + n)
= (1/2) lg (T (√n) + 1) + (1/2) lg n
≈ (1/2) lg T (√n) + (1/2) lg n
Теперь давайте определим S (n) = lg T (n). Тогда имеем
S (n) = lg T (n)
≈ (1/2) lg T (√ n) + (1/2) lg n
= (1/2) S (√ n) + (1/2) lg n
С этим гораздо проще работать, хотя у нас все еще есть проблема сокращения повторения по силам каждый раз. Чтобы решить эту проблему, давайте сделаем еще одну замену, которая является довольно распространенной при работе с такими выражениями. Давайте определим R (n) = S (2 n ). Тогда имеем
R (n) = S (2 n )
≈ (1/2) S (√2 n *) 1138 *) + (1/2) lg 2 n
= (1/2) S (2 n / 2 ) + (1/2) n
= (1/2) R (n / 2) + (1/2) n
Отлично! Теперь осталось только решить R (n).
Теперь здесь есть небольшой улов. Мы могли бы немедленно использовать основную теорему, чтобы заключить, что R (n) = Θ (n). Проблема в том, что знание того, что R (n) = Θ (n), не позволит нам определить, что такое T (n). В частности, давайте предположим, что мы просто знаем R (n) = Θ (n). Тогда мы могли бы сказать, что
S (n) = S (2 lg n ) = R (lg n) = Θ (log n)
чтобы получить S (n) = Θ (log n). Тем не менее, мы застряли при попытке решить для T (n) в терминах S (n). В частности, мы знаем, что
T (n) = 2 S (n) = 2 Θ (log n) ,
но мы не можем go из этого сказать, что T (n) = Θ (n). Причина в том, что скрытый коэффициент в log (log n) является существенным здесь. В частности, если S (n) = k lg n, то имеем
2 k lg n = 2 lg n k = n k ,
, поэтому главный коэффициент логарифма будет в конечном итоге определять показатель степени для полинома. В результате при решении R нам нужно определить точный коэффициент линейного члена, который переводит в точный коэффициент логарифмического c члена для S.
Так что давайте вернемся к R (n ), который мы знаем
R (n) ≈ (1/2) R (n / 2) + (1/2) n.
Если мы повторим это несколько раз, и мы увидим эту схему:
R (n) ≈ (1/2) R (n / 2) + (1/2) n
≈ (1/2) ((1/2) R (n / 4) + (1/4) n) + (1/2) n
≈ (1/4) R (n / 4) + (1/8) n + (1/2) n
≈ (1/4) ((1/2) R (n / 8) + n / 8) + (1/8) n + (1/2) n
≈ (1/8) R (n / 8) + (1/32) n + (1/8) n + (1/2) n.
Похоже, что после k итераций мы получаем, что
R (n) ≈ (1/2 k ) R (n / 2 k ) + n (1/2 + 1/8 + 1/32 + 1/128 + ... + 1/2 2k + 1 ).
Это означает, что мы должны посмотреть на сумму
(1/2) + (1/8) + (1/32) + (1/128) + ...
Это
(1/2) (1 + 1/4 + 1/16 + 1/64 + ...)
, который, как сумма геометрии серии c, решает до
(1/2 ) (4/3)
= 2/3 .
Эй, смотри! Это те 2/3, о которых мы говорили ранее. Это означает, что R (n) составляет примерно (2/3) n + c для некоторой константы c, которая зависит от базового случая рецидива. Поэтому мы видим, что
T (n) = 2 S (n)
= 2 S (2 lg n *) 1251 *)
= 2 R (lg n)
≈ 2 (2/3) lg n + c
= 2 LG N 2/3 + c
= 2 c 2 lg n 2/3
= 2 c n 2/3
= Θ (n 2/3 )
Что соответствует теоретически предсказанным и эмпирически наблюдаемым значениям из предыдущих.
Это была очень забавная проблема проработать, и я признаю, что я удивлен ответом! Я немного нервничаю, хотя, возможно, я что-то упустил при переходе от
lg T (n) = (1/2) lg (T (√n) + 1) + (1 / 2) lg n
до
lg T (n) ≈ (1/2) lg T (√ n) + (1/2) lg n.
Возможно, этот термин +1 фактически вводит какой-то другой термин в повторение, которое я не узнал. Например, есть ли термин O (log log n), который возникает в результате? Это меня не удивит , учитывая, что у нас есть повторение, которое уменьшается на квадрат root. Тем не менее, я провел несколько простых исследований данных, и я не вижу здесь никаких терминов, которые выглядят так, будто в них используется двойной журнал.
Надеюсь, это поможет!