初始算法

算法时间复杂度

我们称指数函数为爆炸增量函数。想一想，如果算法的时间复杂度是O(2^n)会怎样？随着n的增长，算法会不会“爆掉”？我们经常见到有些算法调试没问题，运行一段时间也没问题，但在关键的时候宕机(shutdown）。

例如 在线考试系统，50人考试没问题，100人考试也没问题，但如果全校10000人考试就可能宕机。

注意：宕机就是死机，指计算机无法正常工作，包括一切原因导致的死机。计算机主机出现意外故障而死机，一些服务器（如数据库服务器）死锁，服务器的某些服务停止运行等，都可以称为宕机。

常见的算法时间复杂度有以下几类。

（1）常数阶。

常数阶算法的运行次数是一个常数，如5、20、100。常数阶算法的时间复杂度通常用O(1)表示。

（2）多项式阶。

很多算法的时间复杂度是多项式，通常用0(n)、O(n^2)、 O(n^3)等表示。

（3）指数阶。

指数阶算法的运行效率极差，程序员往往像躲“恶魔”一样避开这种算法。指数阶算法的时间复杂度通常用0(2^n)、O(n!)、 O(n^n)等表示。

（4）对数阶。

对数阶算法的运行效率较高，通常用O(logn)、O(nlogn)等表示。

指数阶增量随着X的增加而急剧增加，而对数阶增长缓慢。它们之间的关系如下：

== 在设计算法时，我们要注意算法复杂度增量的问题，尽量避免爆炸级增量。==

斐波那契数

斐波那契数列入下：

1，1，2，3，5，8，13，21，34，…

递归表达式如下：

算法设计

首先按照递归设计一个算法，如下

//算法1.1
int Fib1(int n){
    if(n==1||n==2)   
    return 1;
    return Fib1(n-1)+Fib1(n-2);
}

我们设计完算法后应该考虑如下问题：

1. 算法是否正常？
2. 算法复杂度如何？
3. 算法能否改进？

算法验证分析

上面需要考虑的第1个问题毋庸置疑，因为算法1-1是完全按照递推公式写出来的，所以正确性没有问题。那么算法复杂度呢？假设T(n)表示计算Fib1(n)所需的基本操作次数，那么:

n=1时，T(n)=1；
n=2时，T(n)=1；
n=3时，T(n)=3；//调用Fib1(2)和Fib1(1)并执行一次加法运算（Fib1(2)+Fib1(1)）

因此，当n>2时需要分别调用Fib1(n-1)和Fib1(n-2)并执行一次加法运算，换言之：

n>2时，T(n)=T(n-1)+T(n-2)+1；

递归表达式和时间复杂度T(n)的关系如下：

所以T(n)>=F(n)。

通过求出斐波那契数列的通项公式：

因为T(n)>=F(n)，所以这是一个指数阶的算法!

算法改进

因此需要改进一下算法，我们可以采用迭代法进行算法设计，见算法1-2。

//算法1-2 
int Fib3(int n){
    if(n==1||n==2)   
         return 1;
    int s1=1; //用s1和s2记录前面的两项
    int s2=1;
    for(int i=3;i<=n;i++){
         int tmp=s1+s2;
         s1=s2;
         s2=tmp;
    }
    return s2;
}

算法1-2使用了几个辅助变量进行迭代，时间复杂度为0(n)，但空间复杂度降到了O（1）。

• 如对算法有兴趣欢迎参加本次活动，了解更多知识。