有人能帮忙解决这个递归关系吗?(涉及IT技术)

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

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

在第一个问题中,我使用了替换法来计算n、logn等,但所有的答案都是错误的。
递归树:我不确定能否应用,因为根节点将是一个常数。

有人可以帮忙吗?


3
我建议关闭这个问题,因为它是一个数学问题,而不是一个编程问题。 - ProgramFOX
6个回答

11
使用 Master Theorem 来解决这种递归关系。
给定形式为:
  • T (n) = a T(n/b) + nc .. 如果 n > 1

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

其中,a 是大于或等于 1 的整数,b 是大于 1 的实数,c 和 d 分别是正实数和非负实数。当 n 是 b 的幂时,有以下三种情况:
  1. 如果 logb a < c,则 T (n) = Θ(nc),
  2. 如果 logb a = c,则 T (n) = Θ(nc log n),
  3. 如果 logb a > c,则 T (n) = Θ(nlogb a)。
1) T(n) = 2T(n/2) + 0(1) 在这种情况下,
a = b = 2; logb a = 1; c = 0 (因为 nc =1 => c= 0)
因此,适用情况(3)。所以 T(n) = Θ(n) :)
2) T(n) = T(sqrt(n)) + 0(1) 令 m = log2 n;
=> T(2m) = T( 2m / 2 ) + 0(1) 现在将 K(m) = T(2m) 重命名为 K(m) => K(m) = K(m/2) + 0(1) 应用情况(2)。

即使f(n)是一个常数,比如在这种情况下是0(1),我可以应用主定理吗? 第二个问题呢? - rda3mon
@Ringo:是的,你可以。看看编辑。 - Prasoon Saurav
1
第二部分是不正确的。如果 2^m = t,那么 2^(m/2) 再次等于 sqrt(t)。或者更确切地说,2^m = 2^log n = n,因此替换没有起到任何作用。 - casablanca
非常感谢。但在第二种情况下,您是如何选择 m=lg(n) 的呢?我的意思是如何进行猜测? - rda3mon
@Ringo 他使用了对数规则 - http://www.analyzemath.com/logfunction/logarithm_exponential.html - Irwin
第二部分似乎仍然不正确。这里是解决方案 T(n)=T(\sqrt{n})+1,将n替换为2^{2^k},得到T(2^{2^k})=T(2^{2^{k-1}})+1。现在将T(2^{2^k})替换为S(l),得到S(l)=S(l-1)+1。由于这只是一系列1的序列,递归树的层数可以计算为2^{2^{k-i}}=2,其中i表示层数。解决这个问题后,得到k=i,并且k可以写成log_2(log_2(n))。因此,总和可以表示为1*log_2(log_2(n))。因此,复杂度可以写成\Theta(log(log(n))) - Ramandeep Nanda

11
让我们看第一个。首先,您需要知道T(基本情况)。您提到它是一个常数,但在解决问题时将其写下很重要。通常是类似于T(1)= 1的东西。我会使用它,但您可以概括为任何东西。
接下来,找出您需要重复多少次(也就是递归树的高度)。n是您的问题规模,因此我们可以将n反复除以2几次?在数学上,当n /(2 ^ i)= 1时,i是多少?找到它,稍后再考虑。
接下来,进行一些替换,直到您开始注意到一些模式。
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的情况下步骤的数量是多少?


5

对于第一部分,您可以像@Prasoon Saurav建议的那样使用主定理。

对于第二部分,只需展开递归:

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 nk = log log n。这给出了T(n) = k * O(1) = O(log log n)


1
2^k = log n 是如何推导出 k = log log n 的? - Irwin
@casablanca,你能解释一下 <= 1 是怎么来的吗? - TechCrunch

1

让我们来看看第一个递归式,T(n) = 2T(n/2) + 1。这里的n/2是我们的线索:每个嵌套项的参数都是其父级的一半。因此,如果我们从n = 2^k开始,则在达到基本情况T(0)之前,我们将在我们的展开中有k个术语,每个术语都会将总数增加1。因此,假设T(0) = 1,我们可以说T(2^k) = k + 1。现在,由于n = 2^k,我们必须有k = log_2(n)。因此T(n) = log_2(n) + 1。

我们可以将相同的技巧应用于您的第二个递归式,T(n) = T(n^0.5) + 1。如果我们从n = 2^2^k开始,则在我们的展开中将有k个术语,每个术语都会将总数增加1。假设T(0) = 1,我们必须有T(2^2^k) = k + 1。由于n = 2^2^k,我们必须有k = log_2(log_2(n)),因此T(n) = log_2(log_2(n)) + 1。


0

大多数情况下,处理递归的最佳方法是绘制递归树并仔细处理基本情况。

但是在这里,我将给您一些使用替换法解决问题的提示。

在递归中,首先尝试替换n = 2^k 在递归中,其次尝试替换n = 2^2^k


0

递归关系和递归函数都应该从f(1)开始解决。在情况1中,T(1) = 1; T(2) = 3; T(4) = 7; T(8) = 15; 很明显,T(n) = 2 * n -1,这在O符号表示法中是O(n)。
在第二种情况下,T(1) = 1; T(2) = 2; T(4) = 3; T(16) = 4; T(256) = 5; T(256 * 256) =6; 很快就会发现T(n) = log(log(n)) + 1,其中log以2为底。显然,这是O(log(log(n)))的关系。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接