2.1 算法定义

算法是解决特定问题求解步骤的描述，计算机中表现位指令的有限序列，并且每条指令表示一个或多个操作。

2.2 算法的特性

算法具有：输入、输出、有穷性、确定性和可行性。

2.2.1 输入输出

算法具有零个或多个输入和至少一个或多个输出。

2.2.2 有穷性

指的是算法在执行有限步骤之后，自动结束而不会出现无限循环，并且每一个步骤可接受在时间内完成。

2.2.3 确定性

算法的每一步骤具有确定的含义，不会出现二义性。

2.2.4 可行性

算法的每一步都必须可行的，每一步都能狗通过执行有限次数完成。

2.3 算法设计的要求

2.3.1 正确性

指的是至少具有输入、输出和加工处理无歧义性，能正确反映问题的需求，能够得到问题的正确答案。

2.3.2 可读性

算法设计的另外一个目的，为了便于阅读、理解和交流。

2.3.3 健壮性

输入数据不合法，算法也能够做出相关处理，而不是产生异常或者莫名其妙的结果。

2.3.4 时间效率高和存储量低

时间效率高：算法的执行时间。存储量低：执行过中需要的最大存储控件，运行时所占用的内存或外部硬盘存储控件。

应该满足时间效率和存储量低的需求。

2.4 算法效率的度量方法

2.4.1 事后统计方法

通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行对比，确定算法效率的高低。

2.4.2 事前分析估算方法

在计算机程序编制前，依据统计方法对算法进行估算。

一个程序的运行时间，依据赖与算法的好坏和问题的输入规模。问题输出规模是指输入量的多少。

2.5 函数的渐近增长

给定义两个函数f（n）和g（n），如果存在一个整数N，使得对于所有的n>N，f（n）总是大于g（n），所以f（n）的增长渐近快于g（n）。

判断一个算法效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项） 的阶数。

可以分析出：某个算法，随着n的增大，它会优越于另外一个算法，或者差于另外一个算法。

2.6 算法时间的复杂度

2.6.1 算法时间复杂度定义

在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并而确定T（n）的数量级。算法的时间复杂度（时间量度），记作T（n）=O（f（n））。表示随着问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称为算法的渐近时间赋值度，简称时间复杂度。其中f（n）是问题规模n的某个函数。

2.6.2 推导大O阶方法

推导大O阶：

（1）常数1取代运行时间中的所有加法常数。

（2）在修改后运行次数函数中，只保留最高阶项。

（3）如果最高阶项存在且系数不是1，则去除与这个项相乘的系数，得到结果最大O阶。

2.6.3 常数阶

1
2
3

int sum = 0,n = 100;  //一次
sum = (1 + n) * n /2; //一次
printf("%d", sum);    //一次