算法定义
算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或者多个操作。
算法的特性
- 输入和输出
算法具有零个或多个输入，但是至少有一个输出，算法是一定需要输出的，输出的形式可以是打印，后者返回值
- 确定性
算法的每个步骤都具有确定的含义，不会出现二义性，一个条件下之意一条执行路径，相同的输入也只能有唯一的结果，诶个步骤都被精准定义而不会有歧义。
- 有穷性
算法在执行有限步骤后，自动结束不会出现无限循环，并且每一步都在可接受的时间内完成。有穷指的是实际应用当中合理的、在可行方案中是最优的有边界。
- 可行性
算法的每一步都是能够通过执行有限次数完成的，并能得到正确的结果
算法的设计要求
- 正确性
1、算法程序没有语法错误：最基本的要求
2、对于合法的输入数据能得到正确的结果
3、对于非法的输入数据能得出满足规格说明的结果，也就是做了特殊数据的判断处理。
- 可读性
便于阅读、理解和交流。我们写代码的目的，出列让计算机执行外还有一个更重要的目的是为了便于他人阅读，让人理解和交流。
可读性是算法（也包括代码）好坏很重要的标志。
- 健壮性
好的算法应该对输入数据不合法的情况做合适的处理。
- 时间效率高，占用存储少。
算法应该尽量满足时间效率高和存储量（包括算法执行过程中占用的内存和硬盘存储空间）低的需求。
算法效率度量方法
一个程序的运行时间，依赖于算法的好坏和输入量的多少
在估计算法执行时间时最可靠的就是计算对运行时间有消耗的基本操作的执行次数。应该把程序看成是执行算法的一系列步骤，然后建立基本操作数量与输入量多少的关系函数。
判断一个算法效率的时候，一般都更关注最高阶项，忽略函数中的常数项和其他次要项。
算法的基本操作次数y与输入量的多少x有很大关系。例：
两个算法S1、S2的基本操作次数y1、y2,输入量x，可能存在某个n值的存在，当x>n的时候总有y1>y2,又或者y2>y1，因此评估算法的执行次数的时候应该看具体的输入量多少。
算法的时间复杂度
时间复杂度是算法的时间度量。
推导O( )的技巧：
1.用常数1代替所有的加法项的常数。
2.在修改后的函数中，去掉次要项，只保留最高项。
3.使最高项为1，得到的就是O( )。
网友评论