一、概述

1. 算法表述

• 自然语言（ENGLISH）
• 算法描述语言（Pseudo-code）
• 计算机程序语言(C++,Java)
• 硬件设计（DSP）

2. 算法一般特性

• **正确性：**对于符合输入类型的任意输入数据，都产生正确的输出
• **有效性：**每一步指令能够被有效的执行，并且规定了指令的执行效果，结果应该具有的数据类型，而且是可以预期的
• **确定性：**每一步之后都要有确定的下一步指令
• **有穷性：**有限步内结束

3. 算法效率

1. 有限资源

• 计算时间
• 存储空间
• 网络带宽

2. 资源开销与输入

• **资源开销与输入大小相关：**文本长度、排序记录条目数量
• **资源开销与输入的组织结构有关：**无序、有序

4. 渐进分析

1. 渐进分析目的

• n：问题规模
• T（n）：资源开销函数
• f（n）：问题规模的整函数表达式

2. 渐进分析与阶的增长

• 开销函数的估计是相对的而不是绝对的
• 独立于机器的算法开销估计
• 独立于实现技术的算法自身测度表示
• 关心的是大规模输入的情况

3. 符号表示

• $O$ 记号：f(n) = O(g(n)) if ∃c > 0, n0 > 0, ∀n ≥ n0: 0 ≤ f(n) ≤ c ⋅ g(n)
• $Ω$ 记号：f(n) = Ω(g(n)) if ∃c > 0, n0 > 0, ∀n ≥ n0: 0 ≤ c ⋅ g(n) ≤ f(n)
• $Θ$ 记号：f(n) = Θ(g(n)) if ∃c1, c2 > 0, n0 > 0, ∀n ≥ n0: c1 · g(n) ≤ f(n) ≤ c2 ⋅ g(n)
• $ω$ 记号：f(n) = ω(g(n)) if ∀c > 0 ∃n0 > 0, ∀n ≥ n0: f(n) ≥ c ⋅ g(n)
• $o$ 记号：f(n) = o(g(n)) if ∀c > 0 ∃n0 > 0, ∀n ≥ n0: f(n) ≤ c ⋅ g(n)

$o 或 w 对比 O 或 Θ$

• $f(n) = O(f(n)) ; f(n) = Ω(f(n)) ; f(n) = Θ(f(n))$
• $f(n) = O(g(n)) 且 g(n) = O(h(n)) ⇒ f(n) = O(h(n))$
• $f(n) = Ω(g(n)) 且g(n) = Ω(h(n)) ⇒ f(n) = Ω(h(n))$
• $f(n) = Θ(g(n)) 且g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n))$
• $ f(n) = O(g(n)) ⇐⇒ g(n) = Ω(f(n))$
• $ f(n) = o(g(n)) ⇐⇒ g(n) = ω(f(n))$
• $f(n) = O(g(n)) 且f(n) = Ω(g(n)) ⇒ f(n) = Θ(g(n))$
• $f1(n) = O(g1(n)) 且f2(n) = O(g2(n)) ⇒ f1(n) + f2(n) = O(g1(n) + g2(n))$
• $f(n) = O(g(n)) ⇒ f(n) + g(n) = O(g(n))$
• $If lim_{n ightarrow+infty} frac{f(n)}{g(n)} = 0, then f(n) = o(g(n))$
• $If lim_{n ightarrow+infty} frac{f(n)}{g(n)} = +infty, then f(n) = w(g(n))$
• $If lim_{n ightarrow+infty} frac{f(n)}{g(n)} = c,∃ c > 0,then f(n) = heta(g(n))$
• $If lim_{n ightarrow+infty} frac{f(n)}{g(n)} = 0,then a^{f(n)} = o(a^{g(n)}),∀a > 1$
• $f(n) = o(g(n)) Rightarrow a^{f(n)} = o(a^{g(n)}),∀a > 1$
• $f(n) = heta(g(n)) !=> a^{f(n)} = o(a^{g(n)}),∀a > 1$

5. 最坏、最好和平均情况

• 输入量为n时的最大运行步骤数目
• 输入量为n时的最小运行步骤数目
• 输入量为n时的平均运行步骤数目

6. 伪代码中的约定

• 缩进表示程序中的分程序（程序块）结构
• while、for、repeat-until 等循环结构和 if、then、else 条件结构与Pascal相同

  for 循环 ： 当循环终止，循环计数器的值为第一个超出 for 循环界限的值 **to 关键字：**每次迭代增加循环计数器值 **downto 关键字：**每次循环减少循环计数器值 **by 关键字：**改变循环计数器的该变量，如：by 2 表示循环计数器改变为 1，3，5…

• // 表示后面部分是注释
• 多重赋值 i=j=e 是将表达式 e 的值赋给变量 i 和 j
• 变量是局部于给定过程的，在没有显示说明的情况下，我们不使用全局变量
• 数组元素是通过“数组名[下标]”这样的形式来进行访问的，数组下标从 1 开始（伪代码中）
• 复合数据组织成对象，对象由属性组成；如：串联访问x.f.g
• 参数采用按值传递方式：被调用的过程会收到参数的的一份副本
• return 语句将控制返回到调用点，允许一个 return 返回多个值（伪代码中）
• 布尔运算符 and 和 or 都具有短路能力，如：

  求表达式 x and y 的值时：

  • 首先计算x的值。如果x的值为FALSE，那么整个表达式的值就不可能为TRUE了，因而就无需再对y求值了
  • 如果x的值为TRUE的话，就必须进一步计算出y的值，才能确定整个表达式的值

• 关键字 error ：表示调用出现错误，调用过程处理该错误

二、排序算法

1. 插入排序

1. 伪代码

2. 详解

3. 时间复杂度

2. 归并排序

1. 伪代码