问题来自王道研究生的数据结构书，思路开阔
斐波那契数列有两种常用的算法：递归算法和非递归算法。 试着分别分析两种算法的时间复杂度。
递归方式递归方式代码：
递归结束条件可以不同，如果数列从开头开始为1，则结束条件如下。
如果从第0个开始，第0个是0，则结束条件会改变。 如果n是0，则返回0；如果n是1，则返回1
# include stdio.h # include stdlib.hint Fibonacci (intn ) if ) n==1|||n==2) return 1； ELSEReturnFibonacci(n-1 ) Fibonacci (n-2 )； }intmain(intargc，char *argv[] ) {int n； scanf('%d '，n )； intresult=Fibonacci(n； printf('%d '，result； 返回0； 时间的复杂性可以用下图分析。
如果是二叉树，则其时间复杂度为o(2^n )。 但是，实际上没有装满二叉树，所以比这个小一点。 网上有正确的值和导出过程，请看一下。
非递归代码如下所示。
# include stdio.h # include stdlib.hint Fibonacci (intn ) if ) n=2) ) {return 1； }else{int num1=1； int num2=1； int i； for(I=2； in； I ) ) {num2=num1 num2； num1=num2-num1； }return num2； }}int main () ) {int n； scanf('%d '，n )； intresult=Fibonacci(n； printf('%d '，result； 直接看for循环即可，由于语句反复执行的次数为n的数量级，所以时间的复杂度为o(n )。