递归算法的复杂度

作者: , 共 1031 字

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

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

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

类似文章:
相似度: 0.112
编程 » C++, 算法
一个短小、高效的 C++ 函数,用来判断指定日期是星期几:
Xie Xie 给我看了一个链接 性能调优 -- 永远超乎想象 ,里面提到了素数筛法的复杂度,作者用实验发现此筛法是线形的。
前面 已经提到了显示中大多数难解问题问题最后都被证明是 NP- 完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在 这篇文章 提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
相似度: 0.060
前两天贴出了一个 硬币游戏 ,希望寻找一种胜利策略。这是一个非常有意思的题目,没事做的时候可以用来锻炼思考能力。我迫不及待的想在这里公布解答,因为我已经把它解决掉了。如果有人还想继续享受思考的乐趣,请飘至 原问题
编程 » Excel
最近看到一个比较有趣的问题, Excel 中以下表达式代表什么含义:
注 : 这个问题来自 China Theory Week 2008 的 Open Problems Session。
数学 » 概率, 测试
所有大学生都应该学的两门课程,一是经济学,二是概率论,这两门课分表代表着一种生活中的思维方式。来测试一下你的概率论学得怎么样吧。题目作者 : wzz12346@newsmth, 原发 Mathematics@newsmth。解答亦来自 wangzz。题目顺序和答案经过调整。