重命名变量以解决递归方法

你所说的一切都是正确的,直到你声称因为S(m)=T(2 ^米 ),则m=2 ^米 .

定义S(m)=T(2的步骤 ^米 )类似于用旧函数f定义一些新函数g。例如,如果你定义一个新函数g(x)=2f(5x),你不是说x=5x。你只是定义了一个新函数,它用f来计算。

让我们看看从这里发生了什么。我们定义了S(m)=T(2 ^米 ). 这意味着

S(m)=T(2 ^米 )

=2吨(√(2 ^米 ))+lg(2 ^米 )

我们可以做一些代数简化来看看

S(m)=2T(2 ^米/2 )+米

利用T和S之间的联系,我们可以看到

S(m)=2S(m/2)+m

请注意,我们最终得到了递归S(m)=2S(m/2)+m,而不是通过在原始递归中用S替换T,而是通过代数替换和简化。

一旦我们到了这里,我们就可以使用主定理来求解S(m),得到S(m)=O(m log m),所以

T(n)=S(lgn)=O(lgn-lg-lgn。

至于你最初是如何想出这个的,这需要练习。关键的见解是,要使用主定理,你需要每次将问题的大小缩小一个常数,因此你需要找到一个将平方根转换为除以常数的变换。平方根是一种求幂运算,对数是专门设计用来将求幂运算转换为乘法和除法的,所以尝试对数或指数代换是合理的。既然你知道了窍门,我想你会在更多的地方看到它。

你也可以把第一个方程除以log(n),得到

T(n)/log(n)=T(sqrt(n))/log(sqrt(n)) + 1

然后使用

S(n) = T(n)/log(n) with S(n) = S(sqrt(n)) + 1

或者以不同的方式

S(k) = T(n^(2^(-k)))/log(n^(2^(-k)))

然后

S(k+1)=S(k)+1

也是众所周知的递归方程。