【趣学算法】第二章 算法之美（下）

14天阅读挑战赛

【趣学算法】第二章 算法之美（下）

1. 一棋盘的麦子

1.1 题目描述

1.2 题目解析

1.3 爆炸增量函数

称上面的函数（1.2中的第一个函数）为爆炸增量函数。

爆炸函数也就是指数函数。数学领域词汇，特点是增长速度特别快。

想一想：如果算法的时间复杂度是
$$O(2^n)$$
会怎样？随着n的增长，算法会不会“爆掉”？当有些算法调试的时候没问题，运行一段时间也没问题，但在关键的时候宕机（shutdown）。

例如，在线考试系统时，50人考试没问题，100人开始也没问题，但是全校10 000人考试就可能宕机。

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

1.4 常见的算法时间复杂度

2. 神奇的兔子数列

2.1 题目描述

2.2 题目分析

这个数列如下有十分明显的特点：从第三个月开始，当月的兔子数=上月兔子数+当月新生兔子数，而当月新生兔子数正好等于上上月的兔子数。因此，前面相邻两项之和便构成后一项，换言之：

当月的兔子数=上月兔子数+上上月的兔子数。

2.3 算法设计

有了上面的公式是否可以写一个算法？

首先按照递归表达设计一个递归算法，见算法1-8。

//算法1-8
int Fib1(int n)
{
    if(n==1||n==2)
    {
        return 1;
    }
    //上月兔子+上上月兔子
    return Fib1(n-1)+Fib1(n-2);
}
1
2
3
4
5
6
7
8
9
10

算法设计完之后，需要考虑如下3个问题：

• 算法是否正确？
• 算法复杂度如何？
• 算法是否改进？

2.4 算法验证分析

算法复杂验证，假设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)）
1
2
3

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

n>2是，T(n)=T(n-1)+T(n-2)+1;
1

再说一句，这个算法递归实现，完全没有价值。

2.4 算法改进

3. 算法学习瓶颈

额，这段你们看书吧。主要是将了数据结构与算法不能孤立的学习。

4. 本章小结

本章还是讲了什么是算法，算法的空间复杂度、时间复杂度，以及需要避免的坑。

写在最后，没钱买书，下面的章节是用第一版更新。

本节完。