递归-从斐波那契数列（Fibonacci sequence）问题看剪枝重要性

0.摘要

本文主要通过对斐波那契数列算法复杂度的分析，展示剪枝在递归中的重要性。

 

1.递归求解斐波那契数列问题的时间复杂度。

回顾一下斐波那契数列问题：

斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）

这是一个典型的递归问题，代码非常简单直观：

def F(n):
    if n == 0 or n == 1:
        return 1
    else:
        return F(n-1) + F(n-2)

但是，当我们求解F(100)的时候，就发现程序跑不动了，这是为什么呢？

我们知道：

F(100) = F(99) + F(98)

F(99) = F(98) + F(97)  ; F(98) = F(97) + F(96)  

F(98) = F(97) + F(96)  ; F(97) = F(96) + F(95) ;  F(97) = F(96) + F(95) ; F(96) = F(95) + F(94)  

……

写到这里，各位读者应该看出原因了吧。这样的递归，时间复杂度是O(2^n)的，是一个指数型的时间复杂度

为了更加直观，这里做一下实际仿真：

import time
import matplotlib.pyplot as plt

def F(n):
    if n == 0 or n == 1:
        return 1
    else:
        return F(n-1) + F(n-2)

def run_time(n):
    start = time.time()
    F(n)
    end = time.time()
    return end-start

if __name__ == '__main__':
    run_times = []
    test_num = 30
    for i in range(test_num):
        run_times.append(run_time(i))
    n = range(test_num)
    plt.plot(n,run_times)
    plt.show()

运行后的结果直接显示出了仿真时间的上升趋势。

 

2.剪枝优化

如果我们不使用递归操作，而是借助于for循环，从头开始加，那么结果又会怎么样呢？

def F(n):
    if n == 0 or n == 1:
        return 1
    a,b ,c= 1,1,0
    for _ in range(n-2):
        c = a + b
        a = b
        b = c
    return c

这次的结果显然平和多了。但是，为什么递归求解的时间复杂度如此知道呢？

通过仔细对比，容易发现：

F(100) = F(99) + F(98)

F(99) = F(98) + F(97)  ; F(98) = F(97) + F(96)  

F(98) = F(97) + F(96)  ; F(97) = F(96) + F(95) ;  F(97) = F(96) + F(95) ; F(96) = F(95) + F(94)  

……

不同递归路径下，同一个数值重复计算了多次，这正是时间复杂度高的原因。

如果，我们将已经算过的值保存下来，避免重复计算，这样是不是就能降低复杂度呢？

import time
import matplotlib.pyplot as plt

visited = {}

def F(n):
    if n == 0 or n == 1:
        return 1
    else:
        if n in visited.keys():
            return visited[n]
        else:
            r = F(n-1) + F(n-2)
            visited[n] = r
            return r

def run_time(n):
    start = time.time()
    F(n)
    end = time.time()
    return end-start

if __name__ == '__main__':
    run_times = []
    test_num = 30
    for i in range(test_num):
        run_times.append(run_time(i))
    print(run_times)
    n = range(test_num)
    plt.plot(n,run_times)
    plt.show()

进过剪枝之后的算法，计算时间几乎为0。两者对比，充分体现了搜索过程中，剪枝的重要性！

 

3.跑偏的话题

今天写程序的过程中，在网上找到了一个斐波那契数列在线计算器，结果无意之间发现了个bug。

http://www.99cankao.com/algebra/fibonacci.php

网站上的斐波那契数列在线计算器，在第79项的时候发生了错误。

5527939700884757 + 8944394323791464 = 14472334024676221

但计算器显示的却是14472334024676220。

意外发现，有点小惊喜，记录一下，纯属娱乐了。