算法分析详解

自古老的公元前1世纪开始，《周髀算经》就作为中国最古老的天文学和数学著作。

《周髀算经》采用最简便可行的方法确定天文历法，揭示日月星辰的运行规律，包括四季更替，气候变化，南北有极，昼夜相推的道理。为后来者的生活作息提供了有力保障。

经过几个世纪的发展，到公元9世纪，波斯数学家al-Khwarizmi第一次在数学上提出了“算法”这个概念——演算法。

算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。

在计算机科学中，算法代表用计算机解一类问题的精确、有效的方法。

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。

算法是指令的有限序列，其中每一条指令表示一个或多个操作。

算法有如下几个重要特性：

1.有穷性（每一步必须在有穷的时间内完成）

2.可行性（必须能通过已经实现的基本运算的有限次执行）

3.确定性（每一条指令没有二义性，相同输入必须相同输出）

4.一个算法有零个或者多个输出。

5.一个算法有一个或者多个输入。

一个好算法应该

1.正确性

简单理解为：

程序中没有语法错误，对于几个给定的输入输出都可以正确计算出来，对于精挑细选的带有刁难性的输入也能满足要求计算正确，程序对于一切合法输入都能正确计算出来。

2.可读性

易于理解

3.健壮性

当输入非法数据时，算法会恰当做出反应和处理。而不是中断程序进行。

4.高效性

即用时间复杂度和空间复杂度来衡量代码的高效性（通常两者不可兼得）

时间复杂度 :

即通常所说的算法执行所需要耗费的时间，时间越短，算法越好。

空间复杂度 ：

1.程序保存所需要的存储空间大小。

2.程序在执行过程中所需要消耗的存储空间资源（定义的变量）。

下面列举一些常见的时间复杂度：

常数阶	O(1)
对数阶	O(log2n)
线性阶	O(n)
线性对数阶	O(nlog2n)
平方阶	O(n*n)
立方阶	O(n*n*n)
...	...
k次方阶	O(n的k次方)
指数阶	O(2的n次方)