第二章-算法
第二章 算法
第二章 算法
高斯加法
算法 ：解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法的特性
- 输入：0个或多个
- 输出 ：1个或多个
- 有穷性：自动结束
- 确定性：每一步有确定含义，不会出现二义性
- 可行性：每一步能够通过执行有限次数完成
算法设计的要求
正确性 ：算法满足输入、输出、有穷性、确定性和可行性
没有语法错误（最低要求）
合法输入
→ \to
→ 满足要求的输出结果（次之要求）
非法输入
→ \to
→ 满足说明的输出结果（标准要求）
精心选择甚至刁难的输入
→ \to
→ 满足要求的输出结果（要求最高）
可读性 ：便于阅读、理解和交流
健壮性 ：输入不合法时也能做出相关处理
时间效率高和存储量低 ：降低成本
算法效率的度量方法
事后统计法 ：需事先写好程序，依赖环境，测试数据设计困难
事前分析估计法 ：用统计方法估算
- 策略方法（算法好坏的根本）
- 代码质量（软件支持）
- 输入规模
- 执行速度（硬件性能）
函数的渐近增长
给两个函数
f ( n ) f(n)
f
(
n
) 和
g ( n ) g(n)
g
(
n
) ，如果存在一个整数
N N
N ，使得对于所有的
n
N n\gt N
n
N ，
f ( n ) f(n)
f
(
n
) 总是比
g ( n ) g(n)
g
(
n
) 大，那么，我们说
f ( n ) f(n)
f
(
n
) 的增长渐近快于
g ( n ) g(n)
g
(
n
)
可以忽略加法常数
可以忽略与最高次项相乘的常数
可以忽略所有次高次项
最高次项的指数大的，函数随着 n 的增长，结果也会变得增长特别快
某个算法，随着 n 增大，越来越好于或越来越差于另一算法
算法时间复杂度
算法分析时，语句总执行次数
T ( n ) T(n)
T
(
n
) 是问题规模
n n
n 的函数，其数量级可作为算法时间复杂度的度量，记作
T ( n )
O ( f ( n ) ) T(n)=O(f(n))
T
(
n
)
=
O
(
f
(
n
)) ，
f ( n ) f(n)
f
(
n
) 是问题规模
n n
n 的某个函数，这种记法称为“大 **O O
O** 记法”
非官方名称：
O ( 1 ) O(1)
O
(
1
) ：常数阶
O ( n ) O(n)
O
(
n
) ：线性阶
O ( n 2 ) O(n^2)
O
(
n
2
) ：平方阶
推导大 O O O 阶
- 用常数1取代运行时间中的所有加法常数
- 然后只保留最高次项
- 如果最高次项不是1，则去除该项系数
结果即为其大
O O
O 阶
**常数阶
O ( 1 ) O(1)
O
(
1
)** ：执行三次，不是
O ( 3 ) O(3)
O
(
3
) ，而是
O ( 1 ) O(1)
O
(
1
)
**线性阶
O ( n ) O(n)
O
(
n
)** ：分析循环结构的运动情况
**对数阶
O ( log n ) O(\log n)
O
(
lo g
n
)** ：例循环乘2大于
n n
n 后退出循环，
2 x
n , x
log 2 n 2^x=n, x=\log_2n
2
x
=
n
,
x
=
lo g
2
n
**平方阶
O ( n 2 ) O(n^2)
O
(
n
2
)** ：循环嵌套，如果外部循环次数为
m m
m ，则为
O ( m × n ) O(m\times n)
O
(
m
×
n
)
常见复杂度
| 执行次数函数 | 阶 | 非正式术语 |
|---|---|---|
| 12 12 12 | O ( 1 ) O(1) O ( 1 ) | 常数阶 |
| 2 n + 3 2n+3 2 n + 3 | O ( n ) O(n) O ( n ) | 线性阶 |
| 3 n 2 + 2 n + 1 3n^2+2n+1 3 n 2 + 2 n + 1 | O ( n 2 ) O(n^2) O ( n 2 ) | 平方阶 |
| 5 log 2 n + 20 5\log_2n+20 5 lo g 2 n + 20 | O ( log n ) O(\log n) O ( lo g n ) | 对数阶 |
| 2 n + 3 n l o g 2 n + 19 2n+3nlog_2n+19 2 n + 3 n l o g 2 n + 19 | O ( n log n ) O(n\log n) O ( n lo g n ) | n log n n\log n n lo g n 阶 |
| 6 n 3 + 2 n 2 + 3 n + 4 6n^3+2n^2+3n+4 6 n 3 + 2 n 2 + 3 n + 4 | O ( n 3 ) O(n^3) O ( n 3 ) | 立方阶 |
| 2 n 2^n 2 n | O ( 2 n ) O(2^n) O ( 2 n ) | 指数阶 |
时间复杂度从小到大
O ( 1 ) < O ( log n ) < O ( n ) < O ( n log n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) < O ( n n ) O(1)\lt O(\log n)\lt O(n)\lt O(n\log n)\lt O(n^2)\lt O(n^3)\lt O(2^n)\lt O(n!)\lt O(n^n)
O
(
1
)
<
O
(
lo g
n
)
<
O
(
n
)
<
O
(
n
lo g
n
)
<
O
(
n
2
)
<
O
(
n
3
)
<
O
(
2
n
)
<
O
(
n
!)
<
O
(
n
n
)
最坏情况与平均情况
最坏情况 是一种保证，非特殊说明，都是指坏时间复杂度
平均情况 最有意义，它是期望的运行时间
算法空间复杂度
计算算法所需的存储空间实现，记作
S ( n )
O ( f ( n ) ) S(n)=O(f(n))
S
(
n
)
=
O
(
f
(
n
)) ，
n n
n 为问题模型，
f ( n ) f(n)
f
(
n
) 为关于
n n
n 所占存储空间的函数
当不用限定语地使用 “复杂度” 时，通常都是指时间复杂度