【算法设计与分析】绪论

桃扇骨 2023-07-13 03:09 110阅读 0赞

## 算法理论的两大论题： ##

*  算法设计——对于一个问题如何设计一个有效的算法
 *  算法分析——如何评价或判断一个算法的优劣

## 算法及其重要特性 ##

**算法（Algorithm）**：对特定问题求解步骤的一种描述，是指令的有限序列。  
**算法的五大特性**：

*  输入：一个算法有零个或多个输入。
 *  输出：一个算法有一个或多个输出。
 *  有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
 *  确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。
 *  可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

## 算法的描述方法 ##

**⑴ 自然语言**  
优点：容易理解  
缺点：冗长、二义性  
使用方法：粗线条描述算法思想  
注意事项：避免写成自然段  
**⑵ 流程图**  
优点：流程直观  
缺点：缺少严密性、灵活性  
使用方法：描述简单算法  
注意事项：注意抽象层次  
**⑶ 程序设计语言**  
优点：能由计算机执行  
缺点：抽象性差，对语言要求高  
使用方法：算法需要验证  
注意事项：将算法写成子函数  
**⑷ 伪代码——算法语言**  
伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。  
优点：表达能力强，抽象性强，容易理解

## 算法分析 ##

**算法分析（Algorithm Analysis）**：  
对算法所需要的两种计算机资源——时间和空间进行估算

*  时间复杂性（Time Complexity）
 *  空间复杂性（Space Complexity）

**算法分析的目的**：

*  设计算法——设计出复杂性尽可能低的算法
 *  选择算法——在多种算法中选择其中复杂性最低者

## 时间复杂性分析 ##

问题规模：输入量的多少；  
基本语句：执行次数与整个算法的执行时间成正比的语句  
**大O符号**  
定义：设 f 和 g是定义域为自然数集N上的函数. 若存在正数 c 和 n0，使得对一切 n>=n0，有 0<=f(n)<=c g(n) 成立,  
则称 f(n) 的渐近的上界是 g(n)， 记作  
 f ( n ) = O ( g ( n ) ) f (n) = O(g(n)) f(n)=O(g(n))

**大Ω符号**  
定义：设 f 和 g是定义域为自然数集  
N上的函数. 若存在正数 c 和 n0，使得对一切 n>=n0,有 0<=cg(n)<=f(n)成立, 则称 f(n) 的渐近的下界是 g(n),记作  
 f ( n ) = Ω ( g ( n ) ) f (n) = Ω (g(n)) f(n)=Ω(g(n))

**小o符号**  
定义:设 f 和 g是定义域为自然数集 N上 的函数. 若对于任意正数 c 都存在 n0，使 得对一切 n <= n0,有0 <= f(n) < c g(n) 成立, 则记作  
 f ( n ) = o ( g ( n ) ) f (n) = o(g(n)) f(n)=o(g(n))

**小ω符号**  
定义：设 f 和 g是定义域为自然数集 N上  
的函数. 若对于任意正数 c 都存在 n0，使得对一切 n<= n0,有0 <=cg(n) < f(n)成立, 则记作  
 f ( n ) = ω ( g ( n ) ) f (n) = ω (g(n)) f(n)=ω(g(n))

**θ符号**  
若 f (n) = O (g(n)) 且 f (n) = Ω (g(n)), 则记作  
 f ( n ) = θ ( g ( n ) ) f (n) = θ (g(n)) f(n)=θ(g(n))