【趣学算法】一棋盘的麦子

朴灿烈づ我的快乐病毒、 2023-09-24 13:51 33阅读 0赞

[14天阅读挑战赛][14]  
*努力是为了不平庸~  
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！*

### 案例背景 ###

> 有一个古老的传说，一位国王的女儿不幸落水，水中有很多鳄鱼，国王情急之下下令：“谁能把公主救上来，就把女儿嫁给他。”很多人纷纷退让，一个勇敢的小伙子挺身而出，冒着生命危险把公主救了上来，国王一看是个穷小子，想要反悔，说：“除了女儿，你要什么都可以。”小伙子说：“好吧，我只要一棋盘的麦子。您在第1个格子里放1粒麦子，在第2个格子里放2粒，在第3个格子里放4粒，在第4个格子里放8粒，以此类推，每一个格子里麦子的粒数都是前一格子里麦子粒数的两倍。把这64个格子放满了就行，我就要这么多。”国王听后哈哈大笑，觉得小伙子的要求很容易满足，满口答应。结果发现，把全国的麦子都拿来，也填不完这64个格子……国王无奈，只好把女儿嫁给了这个小伙子。

### 分析 ###

上面这个古老的传说，大概意思，应该每个人都能读懂它所讲的内容吧。

一个棋盘，64 个格子，从第一格，开始，第一格放 1 粒麦子，以此类推，之后每一个放的麦子数是前面格子里麦子数目的 2 倍。

咱们先来探讨这个案例背景中的 64 个格子全部放完需要多少粒麦子呢？

从这个简单案例中，我们可以找到一个规律，每个格子里放的麦子数目为 ***![2^\{i-1\}][2_i-1]***, ![i][] 代表第几个格子。

所以把每一个格子里需要放的麦子粒数加起来，总和为 *S*，则：

*S = ![2^\{0\}+2^\{1\}+2^\{2\}+2^\{3\}][2_0_2_1_2_2_2_3]……![\+2^\{63\}][2_63]* ①

对公式 ① 等号的两边乘以 2 ，等式仍然成立：

2*S = ![2^\{1\}+2^\{2\}+2^\{3\}][2_1_2_2_2_3]……![\+2^\{63\}][2_63]*![\+2^\{64\}][2_64] ②

用公式 ② 减去公式 ① ，得：

*S = ![2^\{64\}-2^\{0\}=][2_64_-2_0]*18 446 744 073 709 551 615。

上面是计算出的一共多少粒麦子，接下来我们换算一下，可以有个更直观的数据量的概念。

据专家统计，每颗麦粒的平均重量约 41.9 毫克，这些麦粒的总重量为：

18 446 744 073 709 551 615 ![\\times][times] 41.9＝772 918 576 688 430 212 668.5（毫克）≈7729 000（亿千克）

全世界人口按 77 亿计算，每人差不多可以分得100 000千克（即100吨）！

我们称这样的函数为**爆炸增量函数**。想一想，如果算法的时间复杂度是![O(2^\{n\})][O_2_n]会怎样？随着 ![n][] 的增长，算法会不会“爆掉”？我们经常见到有些算法调试没问题，运行一段时间也没问题，但在关键的时候宕机（shutdown）。例如在线考试系统，50人考试没问题，100人考试也没问题，但如果全校10 000人考试就可能宕机。

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

### 总结 ###

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

（1）常数阶。

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

（2）多项式阶。

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

（3）指数阶。

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

（4）对数阶。

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

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

![O(1)][O_1]< ![O(logn)][O_logn]< ![O(n)][O_n]<![O(nlogn)][O_nlogn]<![O(n^2)][O_n_2]<![O(n^3)][O_n_3]<![O(2^n)][O_2_n 1]<![O(n!)][O_n 1]<![O(n^n)][O_n_n]

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

[14]: https://marketing.csdn.net/p/bb9f9e25975dba9f9b87f5272afded16
[2_i-1]: https://latex.csdn.net/eq?2%5E%7Bi-1%7D
[i]: https://latex.csdn.net/eq?i
[2_0_2_1_2_2_2_3]: https://latex.csdn.net/eq?2%5E%7B0%7D&plus;2%5E%7B1%7D&plus;2%5E%7B2%7D&plus;2%5E%7B3%7D
[2_63]: https://latex.csdn.net/eq?&plus;2%5E%7B63%7D
[2_1_2_2_2_3]: https://latex.csdn.net/eq?2%5E%7B1%7D&plus;2%5E%7B2%7D&plus;2%5E%7B3%7D
[2_64]: https://latex.csdn.net/eq?&plus;2%5E%7B64%7D
[2_64_-2_0]: https://latex.csdn.net/eq?2%5E%7B64%7D-2%5E%7B0%7D%3D
[times]: https://latex.csdn.net/eq?%5Ctimes
[O_2_n]: https://latex.csdn.net/eq?O%282%5E%7Bn%7D%29
[n]: https://latex.csdn.net/eq?n
[O_1]: https://latex.csdn.net/eq?O%281%29
[O_n]: https://latex.csdn.net/eq?O%28n%29
[O_n_2]: https://latex.csdn.net/eq?O%28n%5E2%29
[O_n_3]: https://latex.csdn.net/eq?O%28n%5E3%29
[O_2_n 1]: https://latex.csdn.net/eq?O%282%5En%29
[O_n 1]: https://latex.csdn.net/eq?O%28n%21%29
[O_n_n]: https://latex.csdn.net/eq?O%28n%5En%29
[O_logn]: https://latex.csdn.net/eq?O%28logn%29
[O_nlogn]: https://latex.csdn.net/eq?O%28nlogn%29