技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 尾递归对时间与空间复杂度的影响

尾递归对时间与空间复杂度的影响

浏览:1721次  出处信息

    以前我也在博客上简单谈过“尾递归”及其优化方式方面的话题。前几天有同学在写邮件向我提问,说是否所有的递归算法都能改写为尾递归,改写成尾递归之后,是否在时间和空间复杂度方面都能有所提高?他以斐波那契数列为例,似乎的确是这样的情况。我当时的回答有些简单,后来细想之后似乎感觉有点问题,而在仔细操作之后发现事情并没有理论上那么简单,因此还是计划写篇文章来讨论下这方面的问题。

斐波那契数列

    大家对于斐波那契数列(Fibonacci)的认识一定十分统一,唯一的区别可能仅在于n是从0开始还是从1开始算起。这里我们使用维基百科上的标准递归定义

    其边界情况为:

    使用这个定义可以直接写出程序,这里我们用F#来表达:

let rec fib n =
    if n < 2 then n
    else fib (n - 1) + fib (n - 2)

    这个算法最容易理解,但其时间复杂度确是:

    这种指数级的时间复杂度在实际应用中是十分可怕的(虽然这个数字是美妙的黄金分割)。因此,我们如果真要“计算”斐波那契数列第n项的值(即不使用“通项公式”),则往往会使用迭代的方式进行,写作尾递归则是:

let fibTail n = 
    // 第i项的值v1,以及即将累加上去的值v2
    let rec fibTail\\\' i v1 v2 =
        if i >= n then v1
        else fibTail\\\' (i + 1) (v1 + v2) v1
    fibTail\\\' 0 0 1

    从代码上也可以轻易地判断出,这个算法的时间复杂度是O(n),实际上它也会被F#或是Scala等支持尾递归的编译器优化为循环操作。这里我们使用命令式编程语言C#来表达编译后的结果:

static int FibTail(int n, int i, int v1, int v2)
{
    while (i < n)
    {
        int temp = v1 + v2;
        v2 = v1;
        v1 = temp;
        i++;
    }

    return v1;
}

    时间复杂度从O(1.618n)降低到O(n),可谓是质的飞跃。

尾调用对空间复杂度的影响

    那么,在空间复杂度方面,尾递归带来什么优化吗?我们首先还是来分析标准的递归算法:

    假设,我们知道,在一个(无副作用的)方法执行完毕之后,除了返回值以外的空间会完全释放出来,因此在fib(n - 2)执行结束之后,它的空间占用是常数级的。且fib(n - 1)的空间占用一定大于fib(n - 2),假设其fib(n)的空间占用为S(n),可得:

    于是fib的空间复杂度是显而易见的O(n)。这个空间复杂度其实并不大,例如经典的归并排序算法的空间复杂度也同样是O(n)。但不幸的是,这里的递归操作占用的完全是栈空间,而栈空间的大小是极其有限的(例如一个Windows应用程序默认情况下只有1M,ASP.NET甚至只有250K)。因此,只需一个稍大一点的数字会产生栈溢出。经试验,在我的机器上只需51K便能出现StackOverflowException:

// 50K不会出现StackOverflowException
51 * 1024 |> fib |> printfn \"%d\"

    那么尾递归算法的空间复杂度呢?我们刚才提到,编译器会将尾递归优化成循环,那在实际运行时这个算法的空间复杂度自然是常数级,即O(1)。但这是我们实际观察到的编译器优化后的结果,从理论上说,我们并无法保证这里的尾递归会被优化成循环。因此我们不妨也从“字面”上来理解代码,看看理论上这样的尾递归调用会形成怎样的空间占用。

    对于尾递归来说,理论上我们只能期待它形成“尾调用”。也就是说,针对某个方法的调用(无论是否是递归操作)是父方法的最后一个操作。在这个情况下,我们无需保留父方法当前的栈空间,因此可以将其完全释放。于是,无论调用多少次,只要每次都将栈空间释放(或重用),其空间占用也始终是个常数,即O(1)。

    因此,无论从理论上(从字面上分析)还是实际上(观察编译结果)来说,似乎将斐波那契数列修改为尾递归,能显著地降低时间及空间复杂度,这也是那位同学提出“尾递归能改进时间和空间复杂度”的依据。那么我们重新回顾一下文章开头所提出的两个问题:

  • 每个递归算法都能改写为尾递归吗?
  • 改写为尾递归都能改进时间及空间复杂度吗?
  •     下次我们继续讨论这两个问题。

    建议继续学习:

    1. 尾递归与Continuation    (阅读:1742)
    QQ技术交流群:445447336,欢迎加入!
    扫一扫订阅我的微信号:IT技术博客大学习
    © 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

    京ICP备15002552号-1