算法的定义及分析

原标题：算法的定义及分析

算法的定义

算法是一系列良定义的计算步骤

算法和程序的区别

算法

算法是指解决问题的一种方法或一个过程。
算法是若干指文章来源站点https://www.yii666.com/令的有穷序列，满足性质：

1. 输入：有外部提供的量作为算法的输入。


2. 输出：算法产生至少一个量作为输出。


3. 确定性：组成算法的每条指令是清晰，无歧义的。


4. 有限性：算法中每条指令的执行次数是有限的，执行每条指www.yii666.com令的时间也是有限的。

程序

1. 程序是算法用某种程序设计语言的具体实现。


2. 程序可以不满足算法的性质(4)。


3. 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。


4. 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。

算法的性质

有穷性：算法必须在有限步骤后终止

确定性：算法必须是没有歧义的

可行性：可以机械的一步步执行

算法的表示

自然语言、编程语言、伪文章来源地址51159.html代码

算法的分析

分析原则

1. 统一机器性能


2. 情况最坏分析

算法运行时间仅依赖于输入规模n，表示为T(n)

渐进分析

渐进记号文章来源地址51159.html

常用的复杂性函数

算法分析基本法则

非递归算法：

1. for / while 循环
   循环体内计算时www.yii666.com间循环次数；
   


2. 嵌套循环
   循环体内计算时间*所有循环次数；


3. 顺序语句
   各语句计算时间相加；


4. if-else语句
   if语句计算时间和else语句计算时间的较大者。

来源于：算法的定义及分析