数据结构 二、算法

一、算法定义

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

二、算法特性

输入输出

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

有穷性

在可接受的时间范围内结束，不会出现出现循环

确定性

不会出现二义性

可行性

每一步都能执行有限次数完成

————————————

三、算法设计的要求

正确性

没有语法错误 对于合法的输入数据能够产生满足要求的输出结果 对于精心选择，甚至刁难的测试数据都有满足要求的输出结果

可读性

便于阅读、理解和交流

健壮性

当输入数据不合法时，算法也能做出相关处理

时间效率高和存储量低

————————————

四、算法效率的度量方法

事后统计方法：有很大缺陷，不采用

事前分析估算方法： 在计算机编程前，依据统计方法对算法进行估算

一个程序的运行时间，依赖于算法的好坏和问题的输入规模（所谓问题输入规模是指输入量的多少）

————————————

五、函数的渐进增长

函数的渐进增长：给定两个函数f（n）和g（n），如果存在一个整数N，使得对于所有的n>N，f（n）总是比g（n）大，那么，我们说f（n）的增长快于g（n）

忽略加法常数。 与最高次项相乘的常数不重要。 最高次项的指数大的，函数随着n的增长，结果也会增长特别快

————————————

六、算法时间复杂度

定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进行分析T(n)随n的变化并确定T(n)的数量级。算法的时间爱你复杂度，也就是算法的时间量度，记作：T(n)=O（f(n)）。它随问题的规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数 分类： 常数阶 O（1） 线性阶 O（n） 对数阶 O（logn） 平方阶 O（n²） ————————————

七、最坏情况与平均情况

最坏情况是运行时间的一种保证，情况不能再坏了。 平均运行时间是最有意义的，因为他是期望的运行时间