math - 我对这种重复的替代解决方案是否正确？

Question

我有一个递归关系，如下所示：

T(e ⁿ ) = 2(T(e ^n-1 )) + e ⁿ，其中 e 是自然对数。

为了解决这个问题并找到一个 Θ 界限，我尝试了以下方法：我输入 k=en ^，等式转换为：

T(k)=2T(k/e)+k

然后，我尝试使用主定理。根据主定理，a=2，b=e>2，f(k)=k。因此，对于某些 ε>0，我们有 f(k)=Ω(n ^{log _b a+ε} ) 的情况，因此我们有 T(k)=Θ(f(k))=Θ(k)。然后设 k=n，我们有 T(n)=Θ(n)。我的解决方案有任何错误吗？

Answer 1

让我们一步一步完成。

你有复发

T(e ⁿ ) = 2 T(e ^n-1 ) + e ⁿ

现在，让我们进行变量替换。定义 k = e ⁿ。然后我们得到

T(k) = 2T(k / e) + k

在这种情况下，使用主定理，我们得到 a = 2、b = e 和 f(k) = k。由于 logb a = ln 2 < 1 且 f(k) = Θ(k)，根据主定理，递归求解为 S(k) = Θ(k)。

如果我们现在设置 k = n'，其中 n' 是函数的实际输入，那么我们得到 T(n') = Θ(n)，我们就完成了。所以，是的，数学检查出来了。

希望这可以帮助！