在数据结构课上，我们正在学习如何解决1个变量的递归关系。不幸的是，有些东西似乎是 "突如其来 "的。
例如，有些习题已经告诉你如何替换变量n。
计算n=2^k的T(n)
T(n) = a for n =< 2
T(n)=8T(n2)+bn^2(a和b为> 0)
但有些习题只是给出了T(n)，而没有提供变量n的替换。
T(n) = 1 n =<1
T(n) = 2T(n4) + sqrt(n)
我用迭代法，得出了正确的答案：sqrt(n)+(12)*sqrt(n)*Log(n)。
但是教授解释的时候，她先说。"让n=4^k"，这就是我说的 "出乎意料"。利用这个事实，答案就比较简单了。
但学生该如何得出呢？
这是另一个例子。
T(n)=1 n =<1
T(n)= 2T( (n-1)2 )+ n
在这里我又开始用迭代法，但我无法得出明确的答案，这样看起来更复杂。经过3个步骤的迭代，我得出了这样的结果。
T(n) = 4T( (n-2)4 ) + 2n - 1。
T(n)=8T( (n-3)8 )+3n - 3。
T(n)=16T( (n-4)16 )+4n - 6。
我倾向于说T(i) = 2^i * T( (n-i)2^i ) + i*n - ? 最后这部分我想不通，也许是我弄错了。
然而在她提供的答案中，她又开始了另一个替换。让n = (2^k) -1. 我不明白这是从哪里来的 - 为什么我会这样做？这背后的逻辑是什么？
在所有这些情况下，这些替换都是合理的，因为它们将递归重写为S(k)=aS(k - 1)+f(k)的形式之一。这些递归通常比其他递归更容易解决，因为它们纯粹以S(k - 1)来定义S(k)。
让我们做一些例子来看看这是如何工作的。考虑这个递归。
T(n) = 1 (如果n≤1)
T(n) = 2T(n4) + sqrt(n) (否则)
这里，问题的大小在每次迭代时都会缩小4倍。因此，如果输入是一个完美的四次幂，那么输入将从大小4缩减k 至4k-1从4岁起k-1 至4k-2，等等，直到递归见底。如果我们进行这样的替换，让S(k)=T(4k)，那么我们就可以得到帽子
S(0) = 1
S(k) = 2S(k - 1) + 2k
现在这是一个递归关系，其中S(k)是用S(k - 1)来定义的，这可以使递归更容易解决。
让我们看看你原来的递归。
T(n) = a (n ≤ 2)
T(n) = 8T(n2) + bn2
请注意，递归步骤将n除以2。如果 n 是一个完全的二次幂，那么递归步骤考虑的是 n 之前的二次幂。k)给出
S(k) = a (k≤1)
S(k) = 8S(k - 1) + b22k
请注意S(k)是如何用S(k - 1)来定义的，这是一个更容易解决的递归。在这里选择2的幂是 "自然的"，因为它使递归步骤纯粹地谈论S的前一个值，而不是S的某个任意较小的值。
现在，看看最后一个递归。
T(n) = 1 (n ≤ 1)
T(n) = 2T( (n-1)2 )+n。
我们想做一些替换k=f(n)，使T(f(n))=2T(f(n)-1)+n，问题是如何做到这一点。
通过一些试验和错误，我们得到，设置f(n)=2n - 1符合要求，因为
(f(n) - 1) 2 = ((2)n - 1) - 1) 2 = (2n - 2) 2 = 2n-1 - 1 = f(n) - 1
因此，让k=2n - 1，设S(k)=T(2n - 1），我们得到
S(n) = 1 (如果n≤1)
S(n) = 2S(n - 1) + 2n - 1
希望对大家有所帮助!