递归算法的复杂度

作者:, 发表于

递归算法的复杂度通常很难衡量,一般都认为是每次递归分支数的递归深度次方。但通常情况下没有这个大,如果我们可以保存每次子递归的结果的话,递归算法的复杂性等于不同的节点个数。这也是动态规划算法思想的由来。

看一下下面这个算法题目,据称是百度的笔试题:

简述:实现一个函数,对一个正整数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));

在递归过程中,每个节点可以引出一条或两条分支,递归深度为 \(\log n\) ,所以总节点数为 \(n\) 级别的,但为何还说此递归本身是非常高效的呢?

理解了动态规划的思想,就很容易理解这里面的问题。因为动态规划本质上就是保存运算结果的递归,虽然递归算法经常会有指数级别的搜索节点,但这些节点往往重复率特别高,当保存每次运算的节点结果后,在重复节点的计算时,就可以直接使用已经保存过的结果,这样就大大提高了速度(每次不仅减少一个节点,而且同时消灭了这个节点后面的所有分支节点)。

在这个问题里是什么情况呢?仔细分析就会发现,在整个搜索数中,第 \(k\) 层的节点只有两种可能性 \(n>>k\)\(n>>k - 1\) 。这意味着整个搜索树事实上只有 \(2\log n\) 个节点。所以这个递归算法本质上的运算复杂度只有 \(O(\log n)\) 。这已经是最优的了。

Q.E.D.


上一篇:求平方根倒数的算法2008年9月19日
下面这个求$$1/\sqrt{x}$$的函数号称比直接调用sqrt库函数快4倍,来自游戏Quake III的源代码。 float InvSqrt (float x){ float xhalf = 0.5f*x; int i = *(int*)&

下一篇:PCP - Probabilistic Checkable Proof2008年10月19日
PS: PCP可以说是理论计算机领域近20年来的最重要的结果之一,它给了NP问题一个新的刻画,并且提供了一种证明近似算法下界的方法。下面是yijia写的PCP


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。