重复次数 T(n) = T(n^(1/2)) + 1 [英] Reccurrence T(n) = T(n^(1/2)) + 1
问题描述
我一直在观察这种复发情况,想检查一下我是否采取了正确的方法.
T(n) = T(n^(1/2)) + 1= T(n^(1/4)) + 1 + 1= T(n^(1/8)) + 1 + 1 + 1...= 1 + 1 + 1 + ... + 1(共 rad n 次)= n^(1/2)
所以答案是 n^(1/2) 的 theta 界
提示:假设 n = 22m 或 m = log2log2n,你知道 22m-1 * 22m-1 = 22m 所以,如果你定义 S(m)=T(n) 你的 S 将是:><块引用>
S(m) = S(m-1)+1 →S(m) = Θ(m) →S(m)=T(n) = Θ(log2log2n)
将其扩展为一般情况.
在像 T(n) = T(n/2) + 1 这样的递归中,在每次迭代中,我们将树的高度减少到一半.这导致 Θ(logn).然而,在这种情况下,我们将输入数字除以 2 的幂(不是除以 2),结果是 Θ(log log n).
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)
So the answer would come to theta bound of n^(1/2)
hint: assume n = 22m or m = log2log2n, and you know 22m-1 * 22m-1 = 22m so, if you define S(m)=T(n) your S will be:
S(m) = S(m-1)+1 → S(m) = Θ(m) → S(m)=T(n) = Θ(log2log2n)
extend it for the general case.
In recursion like T(n) = T(n/2) + 1, in each iteration, we reduce the height of the tree to half. This leads to Θ(logn). In this case, however, we divide the input number by a power of two (not by two) so it turns out to be Θ(log log n ).
这篇关于重复次数 T(n) = T(n^(1/2)) + 1的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!