一、什么是算法
瑞士著名的科学家Niklaus Wirth教授曾提出：数据结构+算法=程序。
数据结构是程序的骨架，算法是程序的灵魂。
二、算法的复杂性
例、写一个算法，求以下序列之和：
-1，1，-1，1，…，（-1）^n
算法一：
int sum(int n)
{
int sum=0;
for(int i=1;i<=n;i++)
sum+=pow(-1,i);//表示(-1)^i
return sum;
}
算法二：
int sum(int n)
{
int sum=0;
if(sum%2==0)
sum=1;
else
sum==-1;
return sum;
}
算法是对特定问题求解步骤的一种描述。
算法具有以下特性。
- 有穷性：算法是由若干条指令组成的有穷序列，总是在执行若干次后结束，不可能永不停止。
- 确定性：每条语句都有确定的含义，无歧义。
- 可行性：算法在当前环境条件下可以通过有限次运算来实现。
输入输出：有零个或多个输入以及一个或多个输出。
三、空间复杂度
算法占用的空间大小。
空间复杂度的本意是指算法在运行过程中占用了多少存储空间。算法占用的存储空间包括：输入输出数据；
- 算法本身；
- 额外需要的辅助空间。
输入输出数据占用的空间是必需的，算法本身占用的空间可以通过精简算法来缩减，但缩减的量是很小的，可以忽略不计。算法在运行时所使用的辅助变量占用的空间（即辅助空间）才是衡量算法空间复杂度的关键因素。
四、时间复杂度
算法运行需要的时间。
算法的运行时间主要取决于最高项，小项和常数项忽略不计。
常见的算法时间复杂度有以下几类。
- 常数阶。
常数阶算法的运行次数是一个常数，如5、20、100。常数阶算法的时间复杂度通常用O(1)表示。 - 多项式阶。
很多算法的时间复杂度是多项式，通常用O(n)、O(n²)、O(n³)等表示。 - 指数阶。
指数阶算法的运行效率极差，程序员往往像躲“恶魔”一样避开这种算法。指数阶算法的时间复杂度通常
用O(2")、O(n!)、O(n")等表示。 - 对数阶。
对数阶算法的运行效率较高，通常用O(logn)、O(nlogn)等表示。
指数阶增量随着的增加而急剧增加，而对数阶增长缓慢。它们之间的关系如下：
O(1)<O(logn)<O(n)<O(nlogn)O(n²)<O(n³)<O(2")O(n!)<O(n")
在设计算法时，我们要注意算法复杂度增量的问题，尽量避免爆炸级增量。
本节主要说明了以下问题。
- 将程序执行次数作为时间复杂度衡量标准。
- 时间复杂度通常用渐近上界符号O((n)表示。
- 衡量算法的好坏时通常考查算法的最坏情况。
- 空间复杂度只计算辅助空间。
- 递归算法的空间复杂度需要计算递归使用的栈空间。
- 设计算法时要尽量避免爆炸级增量复杂度。
