递归算法的复杂度

zhiqiang9月 27, 2008 计算机科学

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

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

简述：实现一个函数，对一个正整数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)$ 。这已经是最优的了。

查看更多关于动态规划, 算法分析, 递归的内容。

你可能感兴趣的

求平方根倒数的算法

16条留言 -> 跳到留言表格

At 2008.09.27 16:41, stone said:

复杂度绝对不是对数的。
计算一下n的二进制形如1010101010...101的情形，可以发现复杂度是n^(w) 对某个0<w<1。
此时递归的路径数目满足类似Fibnacci数的递归形式

[Reply]
- At 2008.09.28 00:55, zhiqiang said:
  
  愿听其祥。
  
  你给的那个例子的复杂度为何是 $n^w$ ？
  
  [Reply]
  - At 2008.09.28 10:16, stone said:
    
    你的对数时间不是对那个递归程序的分析吧。
    如果加上记忆化，确实是对数时间的。
    比如这样
    map mem;
    int function(unsigned int n) {
    if (n == 1) return 0;
    if(mem.find(n)!=mem.end())return mem[n];
    if (n%2 == 0) return mem[n]=1 + function(n/2);
    return mem[n]=1 + min(function((n + 1)/2), function((n - 1)/2));
    }
    我说的时间界是对无记忆化的来说的。
    
    [Reply]
    - At 2008.09.28 10:44, zhiqiang said:
      
      那我们的结论是一样的。
      
      更快的连map都不需要，直接用一个 $2\log n$ 的数组即可。
      
      [Reply]
      - At 2008.10.11 13:37, obtuseSword said:
        
        2logn 的数组也不用，只要两个额外空间，因为可以退化为递推。
        比如 31(0) -> 15(2),16(2) -> 7(4),8(3) -> 3(6),4(4) -> 1(8),2(5) -> 1(6). 所以 31 仅需 6 次操作。
        
        [Reply]
        
        At 2008.10.11 17:05, zhiqiang said:
        
        对，发现这个问题越来越简单了，
At 2008.09.28 02:08, zsp said:

int min_cpu(uint n) {
uint i=0;
while(n!=1){
++i;
i+=n%2;
n=n>>1;
}
return i;
}不过用掩码做应该更快

[Reply]
- At 2008.09.28 08:59, zhiqiang said:
  
  这个是什么原理？
  
  [Reply]
- At 2008.09.28 09:00, zhiqiang said:
  
  你这个就是计算n的二进制的1的个数+n的位数？这个算法是错的，随便举个例子就知道了。
  
  [Reply]
  - At 2008.09.28 18:15, zsp said:
    
    100应该是8次,但是用你的函数是6次
    
    100 50 25 24 12 6 3 2 1
    26 13 12...
    14...
    
    [Reply]
At 2008.10.11 12:14, Solrex Yang said:

int function(unsigned int n) {
if (n == 1) return 0;
if (n%2 == 0) return 1 + function(n/2);
return 1 + min(function((n + 1)/2), function((n - 1)/2));
~~~~~既然后面有 /2，应该是节省了两步，这里应该是加 2 吧
}

[Reply]

At 2008.10.12 23:15, epicalkids said:

int function(unsigned int n)
{
    int result;

    if((n%2)==0)
    {
        result = n/2;
        result = n/result/2;
    }
    else
    {
        result = ((n - (n/2)*2) + (n%2))/2;
    }

    return result;
}

[Reply]

At 2008.10.16 11:13, shining said:

楼主的程序不正确。实际运行一下就知道不对

[Reply]
- At 2008.10.16 12:36, zhiqiang said:
  
  固然还真拿着去运行了程序有个小笔误，上面有网友指出来了，一直没改过来，现在改过来了，你再试试看。
  
  [Reply]
At 2008.11.08 22:52, justin said:

现在的也有问题吧缺少了一种情况考虑

[Reply]
At 2008.11.13 19:11, sunny said:

呵呵，貌似楼主的程序还不是最优的。。。

如果不算比较的运算量的话，对于 1111（2）=15这个例子，存在更高效的算法。。。
楼主的程序-> 1111->1110->111->110->11->10->1 (6步)
更优的路径-> 1111->10000->1000->100->10->1 (5步)
所以如果比较时间不考虑的话，对于奇数来说，应该从低位到高位扫一下连续1的个数，
如果大于3，就加1，小于3减1，等于三都一样。

还有，具体的操作都应该使用位运算。

[Reply]

« 一个简单图的三染色算法问题

概率论感觉测试 »

递归算法的复杂度

查看更多关于动态规划, 算法分析, 递归的内容。

16条留言 -> 跳到留言表格

阅微堂