T(n) = 2T(n/2) + 0(1)
T(n) = T(sqrt(n)) + 0(1)
在第一个问题中,我使用了替换法来计算n、logn等,但所有的答案都是错误的。
递归树:我不确定能否应用,因为根节点将是一个常数。
有人可以帮忙吗?
T(n) = 2T(n/2) + 0(1)
T(n) = T(sqrt(n)) + 0(1)
在第一个问题中,我使用了替换法来计算n、logn等,但所有的答案都是错误的。
递归树:我不确定能否应用,因为根节点将是一个常数。
有人可以帮忙吗?
Master Theorem
来解决这种递归关系。T (n) = a T(n/b) + nc .. 如果 n > 1
T(n) = d .. 如果 n = 1
T(n) = 2T(n/2) + 0(1)
在这种情况下,T(n) = Θ(n)
:)T(n) = T(sqrt(n)) + 0(1)
令 m = log2 n;0(1)
现在将 K(m) = T(2m) 重命名为 K(m) => K(m) = K(m/2) + 0(1)
应用情况(2)。2^m = t
,那么 2^(m/2)
再次等于 sqrt(t)
。或者更确切地说,2^m = 2^log n = n
,因此替换没有起到任何作用。 - casablancaT(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 Nanda1 + 2 + 4 + ... + 2 ^ i
的封闭形式吗?我会给你那个;它是(2 ^ i-1)
。这是一个好记住的数字,但是在这里找出它的方法。Prasoon Saurav提到使用主方法是正确的,但重要的是您知道递归关系在说什么。需要问的问题是,在每个步骤中我要做多少工作,并且对于输入大小为n
的情况下步骤的数量是多少?
对于第一部分,您可以像@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 n
或k = log log n
。这给出了T(n) = k * O(1) = O(log log n)
。
让我们来看看第一个递归式,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。
大多数情况下,处理递归的最佳方法是绘制递归树并仔细处理基本情况。
但是在这里,我将给您一些使用替换法解决问题的提示。
在递归中,首先尝试替换n = 2^k
在递归中,其次尝试替换n = 2^2^k
递归关系和递归函数都应该从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)))的关系。