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

Question

我知道重命名将循环转换为您以前见过的变量的想法。

我对第 4 行之前的幻灯片没意见。他们将 T(2^m) 重命名为 S(m) >> 这意味着他们制作了 2^m = m

所以 S(m) 应该是： S(m)= 2T(m^(0.5)) + m

还有 m 我认为我们不应该保持原样，因为它在这里表示 2^m 但它们实际上不是

谁能给我解释一下吗？

还有我怎么知道我应该使用哪些变量来简化我的操作？

Answer 1

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

定义S(m) = T(2^m)的步骤类似于根据旧函数f定义一些新函数g。例如，如果您定义一个新函数 g(x) = 2f(5x)，您并不是说 x = 5x。您只是定义了一个根据 f.

求值的新函数

让我们看看这里会发生什么。我们定义了 S(m) = T(2^m)。也就是说

S(m) = T(2^m)

= 2T(√(2^m)) + lg (2^m)

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

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

并且，使用 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(lg n) = O(lg n lg lg n).

至于您最初是如何想到这个的 - 这只是需要练习。关键的见解是，要使用主定理，您需要每次将问题的规模缩小一个常数因子，因此您需要找到一个将平方根转换为常数除法的转换。平方根是求幂的一种，而对数是专门用来将求幂转化为乘除法的，所以尝试对数或指数代换是合理的。既然您知道了诀窍，我想您会在更多地方看到它。

Answer 2

您也可以将第一个方程除以 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

又是一个well-known递归方程。

Renaming variables to solve recursion method