问证明递归函数的上界复杂度？

EN

一种可能的方法是:假设T的非递归公式，并喜欢它。在那之后，表明你找到的公式是在你想要的大O中。

为了证明，您可以使用归纳，这是快速和容易的情况下。要做到这一点，首先要说明您的公式适用于第一个值(通常是0或1，在您的示例中是1和琐碎的)。

然后，您将看到，如果它适用于任意数n - 1，则它也适用于其继任者n。为此，您使用了T(n)的定义(在您的示例中是T(n) = 2 T(n - 1) + 1)：正如您知道formla对于n - 1保持的那样，您可以用公式替换T(n - 1)的出现。在您的示例中，您将得到(使用公式T(n) = 2^n - 1)

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

正如您所看到的，如果我们假设n适用于n - 1，那么它适用于n - 1。

现在来了归纳的诀窍:我们展示了我们的公式适用于n = 1，并且我们展示了如果它适用于任何n = k - 1，它也适用于k。也就是说，正如我们对1所做的那样，它也被证明为2。正如它在2中得到的证明一样，它也被证明为3。而事实上..。

因此，在我们的证明中，我们并不假定这个术语对n - 1是正确的，我们只是在假设它是真的的情况下，然后给出了一个初始情况的公式，并使用了归纳法。