Reccurrence T（N）= T（N ^（1/2））+ 1 [英] Reccurrence T(n) = T(n^(1/2)) + 1

问题描述

我一直在找这个rec​​currence，并要检查，如果我正在采取正确的方法。

I've been looking at this reccurrence and wanted to check if I was taking the right approach.

T(n) = T(n^(1/2)) + 1
= T(n^(1/4)) + 1 + 1
= T(n^(1/8)) + 1 + 1 + 1
...
= 1 + 1 + 1 + ... + 1 (a total of rad n times)
= n^(1/2)

因此​​，答案会来THETA约束的n ^（1/2）

So the answer would come to theta bound of n^(1/2)

推荐答案

提示：假设N = 2 ^{2 M} 或m =日志 ₂ 日志 ₂ N，你知道2 ^{2 M-1} * 2 ^{2 M-1} = 2 ^{2 M} 因此，如果定义S（M）= T（n）的你的旨意是：

hint: assume n = 2^2m or m = log₂log₂n, and you know 2^2m-1 * 2^2m-1 = 2^2m so, if you define S(m)=T(n) your S will be:

S（米）= S（M-1）1＆RARR; S（米）=＆的Theta;（米）＆RARR; S（M）= T（N）=西塔（登录 ₂ 日志 ₂ N）

S(m) = S(m-1)+1 → S(m) = Θ(m) → S(m)=T(n) = Θ(log₂log₂n)

扩展它的一般情况。

在递归样T（N）= T（N / 2）+ 1，你会减少树高2倍，每次迭代从而导致＆西塔;（LOGN），但在这种情况下，就可以减少输入号的功率两个（不是两次），所以它会与西塔（日志日志N）

In recursion like T(n) = T(n/2) + 1 you will reduce height of tree 2 times in each iteration which leads to Θ(logn) but in this case, you will reduce input number by power of two (not two times) so it will be Θ(log log n ).

这篇关于Reccurrence T（N）= T（N ^（1/2））+ 1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！