有人可以帮助解决这种递归关系吗？

Question

T(n) = 2T(n/2) + 0(1)

T(n) = T(sqrt(n)) + 0(1)

在第一个中,我使用n,logn等的替换方法; 都给了我错误的答案.
重复树:我不知道我是否可以申请,因为根将是一个常数.

有人可以帮忙吗？

Answer 1

使用Master Theorem来解决这样的递推关系.

设a是大于或等于1的整数,b是大于1的实数.设c为正实数, d为非负实数.鉴于表格的再次出现

• 如果n> 1,则T(n)= a T(n/b)+ n ^c ..

• T(n)= d ..如果n = 1

那么对于b的na幂,

1. 如果log _b a <c,T(n)=Θ(n ^c),
2. 如果log _b a = c,则T(n)=Θ(n ^c log n),
3. 如果log _b a> c,则T(n)=Θ(n ^{log _b a}).

1) T(n) = 2T(n/2) + 0(1)

在这种情况下

a = b = 2;
log _b a = 1; c = 0(因为n ^c = 1 => c = 0)

案例(3)适用.所以T(n) = ?(n):)

2) T(n) = T(sqrt(n)) + 0(1)

设m = log ₂ n;

=> T(2 ^m)= T(2 ^m/2)+0(1)

现在重命名K(m)= T(2 ^m)=> K(m)= K(m/2)+0(1)

应用案例(2).

Answer 2

我们来看看第一个.首先,你需要知道T(基本情况).你提到它是一个常数,但是当你解决这个问题时,你必须把它写下来.通常它就像T(1)= 1.我会使用它,但你可以推广到它是什么.

接下来,找出您重复的次数(即递归树的高度).n是你的问题大小,那么我们可以多次将n重复除以2？从数学角度讲,我什么时候n/(2^i) = 1？搞清楚,保留以备日后使用.

接下来,做一些替换,直到你开始注意到一个模式.

T(n) = 2(2(2T(n/2*2*2) + ?(1)) + ?(1)) + ?(1)

好吧,模式是我们将T()乘以2次,并将n除以2次.多少次？i倍.

T(n) = (2^i)*T(n/(2^i)) + ...

对于最后的大-θ术语,我们使用了一个可爱的技巧.看看我们有几个替换的地方,并忽略T()部分.我们想要θ项的总和.请注意,他们加起来(1 + 2 + 4 + ... + 2^i) * ?(1).你能找到封闭的表格1 + 2 + 4 + ... + 2^i吗？我会给你那个; 它是 (2^i - 1).这是一个很好的记忆,但这是你如何弄明白的.

无论如何,总而言之,我们得到了

T(n) = (2^i) * T(n/(2^i)) + (2^i - 1) * ?(1)

如果你i早些时候解决了,那么你就知道了i = log_2(n).把它插入,做一些代数,你就可以了

T(n) = n*T(1) + (n - 1)*?(1).T(1) = 1.所以T(n) = n + (n - 1)*?(1).这是常数的n倍,加上常数加n.我们删除低阶项和常数,所以它是θ(n).

Prasoon Saurav使用主方法是正确的,但重要的是你要知道复发关系的含义.要问的是,我在每一步做了多少工作,以及输入大小的步骤数是多少n？

Answer 3

对于第1部分,您可以使用Master Theorem作为@Prasoon Saurav建议.

对于第2部分,只需扩展重复:

T(n) = T(n ^ 1/2) + O(1)         // sqrt(n) = n ^ 1/2
     = T(n ^ 1/4) + O(1) + O(1)  // sqrt(sqrt(n)) = n ^ 1/4
     etc.

该系列将继续使用,k直到n ^ 1/(2^k) <= 1,2^k = log n或k = log log n.这给了T(n) = k * O(1) = O(log log n).