算法读书笔记-2

ゝ一世哀愁。 2023-09-24 13:22 31阅读 0赞

[14天阅读挑战赛][14]  
*努力是为了不平庸~  
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~*

## 初始算法 ##

### 算法时间复杂度 ###

> 我们称指数函数为爆炸增量函数。想一想，如果算法的时间复杂度是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的增加而急剧增加，而对数阶增长缓慢。它们之间的关系如下：  
![在这里插入图片描述][2b181284d3d24f5c90fc3bc9fccfce34.png]

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

### 斐波那契数 ###

斐波那契数列入下：  
1，1，2，3，5，8，13，21，34，…  
递归表达式如下：  
![在这里插入图片描述][8f2eb307f0054789ad5d8bd5ebc2123f.png]

##### 算法设计 #####

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

//算法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)的关系如下：  
![在这里插入图片描述][3ad3959bc0b441cb8819c99dfbcfec15.png]  
所以T(n)>=F(n)。  
通过求出斐波那契数列的通项公式：  
![在这里插入图片描述][68d99042805f45daa8a867ae5babee60.png]  
因为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）。

*  如对算法有兴趣欢迎参加本次活动，了解更多知识。  
    [14天阅读挑战赛][14]

[14]: https://marketing.csdn.net/p/bb9f9e25975dba9f9b87f5272afded16
[2b181284d3d24f5c90fc3bc9fccfce34.png]: https://img-blog.csdnimg.cn/2b181284d3d24f5c90fc3bc9fccfce34.png
[8f2eb307f0054789ad5d8bd5ebc2123f.png]: https://img-blog.csdnimg.cn/8f2eb307f0054789ad5d8bd5ebc2123f.png
[3ad3959bc0b441cb8819c99dfbcfec15.png]: https://img-blog.csdnimg.cn/3ad3959bc0b441cb8819c99dfbcfec15.png
[68d99042805f45daa8a867ae5babee60.png]: https://img-blog.csdnimg.cn/68d99042805f45daa8a867ae5babee60.png