我在上周的总结里提到了。在“算法总结”中，算法性能分析还没有完成，后面会补上，所以就放在这里。要分析递归的性能，还是分析清楚吧。清楚地！之前在一道面试题中详细解释了递归算法的时间复杂度，讲了递归算法的时间复杂度，没有讲空间复杂度。本文将通过求斐波那契数列和二分法，深入分析一波递归算法的时空复杂度。仔细看完，你会刷新对递归的认识！递归斐波那契数列的性能分析首先让我们看看递归的方式来寻找斐波那契数列。intfibonacci(inti){if(i<=0)return0;if(i==1)return1;returnfibonacci(i-1)+fibonacci(i-2);}对于递归算法，代码一般比较短，来自从算法逻辑上看，使用的存储空间也很小，但运行时需要的内存不一定少。时间复杂度分析让我们来看看这个寻找斐波那契的递归算法的时间复杂度。在解释递归时间复杂度的时候，我们提到递归算法的时间复杂度本质上取决于：递归次数*每次递归的时间复杂度。可以看出，上面代码中的每一次递归都是一次O(1)的操作。让我们看看递归完成了多少次。这里将以i为5作为输入的递归过程抽象成一棵递归树，如图：从图中可以看出f(5)是f(4)和f(3)的加法那么f(4)是由f(3)和f(2)等相加得到的。在这棵二叉树中，每个节点都是一个递归，那么这棵树有多少个节点呢？之前我们也说过，一棵深度为k的二叉树（根据根节点的深度为1）最多可以有2^k-1个节点。所以递归算法的时间复杂度是O(2^n)，非常大。随着n的增加，时间消耗呈指数增长。做个实验，可以有一个直观的感受。以下是C++代码。让我们测试一下。当我们输入n时，这个递归斐波那契代码需要时间。#include#include#includeusingnamespacestd;usingnamespacechrono;intfibonacci(inti){if(i<=0)return0;if(i==1)return1;returnfibonacci(i-1)+斐波那契(i-2);}voidtime_consumption(){intn;while(cin>>n){millisecondsstart_time=duration_cast(system_clock::now().time_since_epoch());fibonacci(n);millisecondsend_time=duration_cast<毫秒>(system_clock::now().time_since_epoch());cout<<毫秒(end_time).count()-毫秒(start_time).count()<<"ms"<#include<计时>#includeusingnamespacestd;usingnamespacechrono;intfibonacci_3(intfirst,intsecond,intn){if(n<=0){return0;}if(n<3){return1;}elseif(n==3){returnfirst+second;}else{returnfibonacci_3(second,first+second,n-1);}}voidtime_consumption(){intn;while(cin>>n){millisecondsstart_time=duration_cast(system_clock::now().time_since_epoch());fibonacci_3(0,1,n);millisecondsend_time=duration_cast(system_clock::now().time_since_epoch());cout<=l){intmid=l+(r-l)/2;if(arr[mid]==x)returnmid;if(arr[mid]>x)returnbinary_search(arr,l,mid-1,x);returnbinary_search(arr,mid+1,r,x);}return-1;}我们都知道二分查找的时间复杂度是O(logn)，那么递归二进制搜索的空间复杂度是多少？我们还是看每次递归的空间复杂度和深度。首先要弄清楚这里的空间复杂度中的n是什么？在二分查找中，n指的是查找数组的长度。也就是代码中的arr数组。可以看出每次递归的空间复杂度主要是参数传入的arr数组，即：O(n)。让我们看看递归的深度。二分查找的递归深度为logn，递归深度为调用栈的长度。那么这段代码的空间复杂度就是n*logn=O(nlogn)。有同学问：为什么网上很多人说递归二分查找的空间复杂度是O(logn)而不是O(nlogn)？其实就是因为有这个数组，我们才可以把这个数组放在外面，而不是递归的放在函数参数里，代码如下：intarr[]={2,3,4,5,8,10,15,17,20};intbinary_search(intl,intr,intn){if(r>=l){intmid=l+(r-l)/2;if(arr[mid]==n)returnmid;if(arr[mid]>n)returnbinary_search(l,mid-1,n);returnbinary_search(mid+1,r,n);}return-1;}看这段代码，arr数组定义为全局变量，而不是放在递归循环，则每层递归的空间复杂度为O(1)，递归深度为O(logn)。空间复杂度为1*logn=O(logn)。小结本章我们详细分析了递归实现的Fibonacci和二分法的空间复杂度，同时也分析了时间复杂度。特别是两个递归实现的斐波那契数列的时间复杂度是完全不能接受的。我们也做过实验验证时间复杂度是O(2^n)，非常耗时。通过本文，你应该对递归算法的时间复杂度和空间复杂度有更深入的了解。
