递归算法的复杂度
source link: https://zhiqiang.org/cs/complexity-of-recursive-algorithm.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
递归算法的复杂度
递归算法的复杂度通常很难衡量，一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大，如果我们可以保存每次子递归的结果的话，递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。
看一下下面这个算法题目，据称是百度的笔试题：
简述：实现一个函数，对一个正整数 n ，算得到 1 需要的最少操作次数：
如果 n 为偶数，将其处以 2 ；如果 n 为奇数，可以加 1 或减 1 ；一直处理下去。
要求：实现函数（实现尽可能高效） int func(unsigned int n)； n 为输入，返回最小的运算次数。
我不确定是不是对 n 的操作次数有一个简单的刻画，尝试着想了一会儿，似乎不太容易想到。但后来发现这个题目本质上不是算法题，而是算法分析题。因为仔细分析可以发现，题目中给的递归构造本身就是非常高效的。
直接按照题目中的操作描述可以写出函数：
int function (unsigned int n)
{
if (n == 1) return 0;
if (n % 2 == 0)
return 1 + function(n / 2);
return 2 + min(function((n + 1) / 2), function((n - 1) / 2));
}
在递归过程中，每个节点可以引出一条或两条分支，递归深度为lognlogn ，所以总节点数为nn 级别的，但为何还说此递归本身是非常高效的呢？
理解了动态规划的思想，就很容易理解这里面的问题。因为动态规划本质上就是保存运算结果的递归，虽然递归算法经常会有指数级别的搜索节点，但这些节点往往重复率特别高，当保存每次运算的节点结果后，在重复节点的计算时，就可以直接使用已经保存过的结果，这样就大大提高了速度（每次不仅减少一个节点，而且同时消灭了这个节点后面的所有分支节点）。
在这个问题里是什么情况呢？仔细分析就会发现，在整个搜索数中，第kk 层的节点只有两种可能性n>>kn>>k 和(n>>k)−1(n>>k)−1 。这意味着整个搜索树事实上只有2logn2logn 个节点。所以这个递归算法本质上的运算复杂度只有O(logn)O(logn) 。这已经是最优的了。
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK