重复次数 T(n) = T(n^(1/2)) + 1 [英] Reccurrence T(n) = T(n^(1/2)) + 1

查看:45
本文介绍了重复次数 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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆