数据结构之算法和算法分析[1]

算法与数据结构的关系紧密在算法设计时先要确定相应的数据结构而在讨论某一种数据结构时也必然会涉及相应的算法下面就从算法特性算法描述算法性能分析与度量等三个方面对算法进行介绍

算法特性

算法(Algorithm)是对特定问题求解步骤的一种描述是指令的有限序列其中每一条指令表示一个或多个操作一个算法应该具有下列特性

⑴有穷性一个算法必须在有穷步之后结束即必须在有限时间内完成

⑵确定性算法的每一步必须有确切的定义无二义性算法的执行对应着的相同的输入仅有唯一的一条路经

⑶可行性算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现

⑷输入一个算法具有零个或多个输入这些输入取自特定的数据对象集合

⑸输出一个算法具有一个或多个输出这些输出同输入之间存在某种特定的关系

算法的含义与程序十分相似但又有区别一个程序不一定满足有穷性例如操作系统只要整个系统不遭破坏它将永远不会停止即使没有作业需要处理它仍处于动态等待中因此操作系统不是一个算法另一方面程序中的指令必须是机器可执行的而算法中的指令则无此限制算法代表了对问题的解而程序则是算法在计算机上的特定的实现一个算法若用程序设计语言来描述则它就是一个程序

[] [] [] [] []