14天阅读挑战赛

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

  解析：

  棋盘上的64个格子究竟需要放多少粒麦子？

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

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

  用式 ②减去式①，得：

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

      18 446 744 073 709551 615 x 41.9 = 772 918 576 688 430212 668.5（毫克）

                  $\approx$ 7729 000（亿千克）

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

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

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

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

  （1）常数阶。

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

  （2）多项式阶。

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

  （3）指数阶。

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

  （4）对数阶。

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

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

         O(1)<O(logn)<O(n)<O(nlogn)<O($n^2$)<O($n^3$)<O($2^n$)<O(n!)<O($n^n$)

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