第 3 章 算法
# 第 3 章 算法
# 3.1 算法
# 3.1.1 引言
# 3.1.2 搜索算法
笔记
- 线性搜索算法
- 二分搜索算法
# 3.1.3 排序
笔记
- 冒泡排序
- 插入排序
- 插入排序的伪代码没有算法导论上的简练
- 从后往前进行比较可以简化代码与逻辑
- 插入排序的伪代码没有算法导论上的简练
# 3.1.4 字符串匹配
# 3.1.5 贪婪算法
笔记
- 最优化问题
🔲 待做事项
- 收银员算法找到最优解对硬币种类的要求
# 3.1.6 停机问题
# 3.2 函数的增长
# 3.2.1 引言
# 3.2.2 大 O 记号
笔记
- 证明过程是找到一个凭证(witness)
# 3.2.3 一些重要函数的大 O 估算
# 3.2.4 函数组合的增长
笔记
- 两个函数相加与相乘的大
估算
# 3.2.5 大 Ω 与大 Θ 记号
笔记
- 同阶的概念
# 3.3 算法的复杂度
# 3.3.1 引言
# 3.3.2 时间复杂度
笔记
- 最坏情形复杂度
- 平均情形复杂度
# 3.3.3 矩阵乘法的复杂度
笔记
- 矩阵链乘法
🔲 待做事项
- 矩阵链乘法的最优解
- 需要查 CLRS
# 3.3.4 算法范型
笔记
- 蛮力算法
# 3.3.5 理解算法复杂度
笔记
- 易解问题与难解问题
- 能用多项式最坏情形复杂度求解的问题称为是易解的
- 不能用多项式最坏情形复杂度求解的问题称为是难解的
- 不可解问题
- P 与 NP
- 易解的问题属于 P 类
- NP 问题指没有发现多项式最坏情形复杂度的算法能求解
- 但却能以在多项式时间内验证解的问题
- NP 完全问题
- 只要任何一个具有 NP 性质的问题能用一个多项式时间最坏情形算法来求解
- 则 NP 类的所有问题都能用多项式时间最坏情形算法来求解
- 可满足性问题是 NP 完全问题的一个例子
- 只要任何一个具有 NP 性质的问题能用一个多项式时间最坏情形算法来求解
- P 与 NP 问题
- 是问 NP 是否等于 P
- 如果
,则存在不能在多项式时间内求解但其解能在多项式时间内验证的问题
🔲 待做事项
- 可满足性问题的具体内容
编辑 (opens new window)