用迭代法求解递归方程T（n）=1，n<=2;T(n)=T(n-1)+T(n-2) n>2

根据递归方程T(n)=T(n-1)+T(n-2)，可以列出以下递推式：
T(3) = T(2) + T(1) = 1 + 1 = 2
T(4) = T(3) + T(2) = 2 + 1 = 3
T(5) = T(4) + T(3) = 3 + 2 = 5
T(6) = T(5) + T(4) = 5 + 3 = 8

以此类推，可以得到T(n)的值。

因此，我们可以写出如下的迭代函数：

int fibonacci(int n) {
    if (n <= 2) {
        return 1;
    }
    int a = 1, b = 1, c;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

这个函数使用类似于斐波那契数列求解的方法，利用循环来迭代计算T(n)的值。时间复杂度为O(n)。

相关问题

如何利用代入法求解递归方程T(n) = 2T(n/2) + n，并分析其渐进阶？

代入法是一种有效的递归方程求解方法，它通过假设一个形式上的解来求得递归方程的精确解，然后利用数学归纳法来验证解的正确性。对于递归方程T(n) = 2T(n/2) + n，我们可以采取以下步骤进行求解：

参考资源链接：[递归方程解的渐进阶分析：算法与方法](https://wenku.csdn.net/doc/2ewdrqytvo?spm=1055.2569.3001.10343)

首先，假设解T(n)的渐进阶为f(n)。由于递归的性质，我们可以推断出f(n)应该包含分治的乘性因子。因此，我们可以假设f(n) = af(n/b) + g(n)的形式，其中a是分治因子，b是分治的子问题大小的因子，g(n)是每层递归中非递归部分的复杂度。

接下来，我们假设T(n) = O(nlogb(a))，即T(n) = O(nlogn)。这个假设是基于Master定理，该定理指出，对于递归方程T(n) = aT(n/b) + f(n)，其中a≥1且b>1，如果存在一个常数ε>0使得f(n) = O(nlog^k(b)n)且k≥-1，则T(n) = Θ(n^log_b(a))，如果k>-1；如果k=-1，则取决于f(n)与nlog^k(b)n的比较。

在我们的例子中，a=2, b=2, f(n)=n，所以k=0，满足k≥-1的条件，因此我们可以使用Master定理来猜测T(n) = Θ(nlog2(2)) = Θ(nlogn)。

然后，我们使用数学归纳法来验证这个猜测。我们假设对于所有小于n的正整数k，T(k) = O(klogk)是成立的。基于这个假设，我们需要证明T(n) = O(nlogn)也是成立的。

对于递归方程T(n) = 2T(n/2) + n，我们可以将T(n/2)替换为O((n/2)log(n/2))，从而得到：
T(n) = 2O((n/2)log(n/2)) + n
T(n) = O(nlog(n/2)) + n
T(n) = O(nlogn - nlog2) + n
T(n) = O(nlogn - n) + n
T(n) = O(nlogn)

因此，我们可以得出结论，对于递归方程T(n) = 2T(n/2) + n，其渐进阶为T(n) = Θ(nlogn)，这与我们最初的猜测相符合。

为了更深入地掌握代入法和递归方程的渐进阶分析，我强烈推荐阅读《递归方程解的渐进阶分析：算法与方法》。这本书不仅详细介绍了代入法，还包含了其他四种求解递归方程的实用方法，如迭代法、套用公式法、差分方程法和母函数法。它为你提供了一个全面的视角来理解和分析递归方程及其渐进阶，是学习和掌握递归算法分析的宝贵资源。

参考资源链接：[递归方程解的渐进阶分析：算法与方法](https://wenku.csdn.net/doc/2ewdrqytvo?spm=1055.2569.3001.10343)

如何使用代入法求解递归方程T(n) = 2T(n/2) + n，并分析其渐进阶？

当你面对递归方程T(n) = 2T(n/2) + n时，代入法是一个非常实用的工具。代入法的核心思想是基于直觉和归纳推理来猜测递归方程的显式解，然后通过数学归纳法来证明这个猜测。针对这个特定的递归方程，我们可以先假设解的形式为T(n) = O(nlogn)，然后尝试通过数学归纳法证明这个假设是正确的。

参考资源链接：[递归方程解的渐进阶分析：算法与方法](https://wenku.csdn.net/doc/2ewdrqytvo?spm=1055.2569.3001.10343)

在证明过程中，首先验证基础情况是否满足，比如对于n=1时，T(1) = 2T(1/2) + 1。这里，我们需要一个具体的初始条件，比如T(1) = 1。如果基础情况成立，接下来假设对于所有小于n的k都成立，即T(k) ≤ cklogk。

然后我们需要验证当n取值为2^m时的情况。假设对于所有的k < 2^m，递归方程的解都满足T(k) ≤ cklogk。通过代入和简化，我们可以尝试证明当n = 2^m时，T(n) ≤ c*nlogn也成立。这通常涉及到一些代数操作和对数法则。

如果证明成功，我们就可以得出T(n) = O(nlogn)是这个递归方程的一个渐进界。实际上，对于这个递归方程，根据主定理，我们知道T(n) = O(nlogn)确实是正确的解的渐进阶。

关于递归方程的渐进阶分析，更深入的内容可以在《递归方程解的渐进阶分析：算法与方法》一书中找到。该书详细介绍了递归方程组解的渐进阶的求法，并且提供了算法时间复杂度的全面分析，涵盖了迭代算法和递归算法，以及母函数法、套用公式法、迭代树法等多种实用的求解方法。通过这本书，你可以更深入地了解和掌握递归方程的渐进阶分析，为算法优化和性能评估打下坚实的基础。

参考资源链接：[递归方程解的渐进阶分析：算法与方法](https://wenku.csdn.net/doc/2ewdrqytvo?spm=1055.2569.3001.10343)