打开算法之门

14天阅读挑战赛

关于算法的基础知识，你得要先了解

算法是对特定问题求解步骤的一种描述。

算法具有以下特性：
1、有穷性：算法是由若干条指令组成的有穷序列，总是在执行若干次后结束，不可能永不停止。
2、确定性：每条语句都有正确的含义，无歧义。
3、可行性：算法在当前环境条件下可以通过有限次运算来实现。
4、输入/输出：有零个或多个输入以及一个或多个输出。

如何知道自己写的算法是好是坏呢？

1、正确性：正确性是指算法能够满足具体问题的需求，程序运行正常，无语法错误，能够通过典型的软件测试，达到预期。
2、易读性：算法遵循标识符命名规则，简洁易懂，注释语句恰当适量，方便自己和他人阅读，便于后期调试和修改。
3、健壮性：算法对非法数据及操作有较好的反应和处理。
4、高效性：指算法运行效率高，即算法运行所消耗的时间短。
5、低存储性：低存储性是指算法所需的存储空间小。对于像手机，平板电脑这样的嵌入式设备，算法如果占用空间过大，则无法运行。算法占用的空间大小被称为空间复杂度。

时间复杂度：算法运行需要的时间

一棋盘的麦子

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

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

常见的时间复杂度有以下几类：
（1）常数阶
常数阶算法的运行次数是一个常数，如5、20、100。常数阶算法的时间复杂度通常用O(1)表示。

（2）多项式阶
很多算法的时间复杂度是多项式，通常用O(n)、O(n²)、O(n³)等表示。

（3）指数阶
指数算法的运行效率极差，通常用O(2ⁿ)、O(n!)、O(nⁿ)等表示。

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

指数阶增量随着x的增加而急剧增加，而对数阶增长缓慢。它们之间的关系如下：
O(1)< O(logn)< O(n)< O(nlogn) < O(n²)< o(n³)< o(2ⁿ)< O(n!)< O(nⁿ)
在设计算法时，我们要注意算法复杂度增量的问题，尽量避免爆炸级增量。

算法学习瓶颈

“算法好难学呀！”，这应该是很多人的心声。

一个原因是，算法本身具有一定的复杂性。另一个就是自己练习太少了。

算法作为一门学问，有两条几乎平行的线索。一条是数据结构（数据对象)︰数、矩阵、集合、串、排列、图、表达式、分布等。另一条是算法策略:贪心策略、分治策略、动态规划策略、线性规划策略、搜索策略等。这两条线索是相互独立的:对于同一个数据对象上不同的问题(如单源最短路径和多源最短路径)，就会用到不同的算法策略（如贪心策略和动态规划策略)﹔而对于完全不同的数据对象上的问题（如排序和整数乘法)，也许就会用到相同的算法策略(如分治策略）。所以想要学好算法的前提先把数据结构学好，学思想，再多敲。

参考资料：https://t.csdnimg.cn/YlcO
一步一步脚踏实地！