设计和分析算法期末复习

算法设计与分析期末复习

目录

算法设计与分析期末复习

第一章

1 算法及其重要特性

2 算法的描述方法

第二章

1 算法的时间复杂性分析

第四章

1 分治法基本思路

2排序问题中的分治法

第五章

1 分治法和减治法区别：

2 查找问题中的减治法

3 排序问题中的减治法

第六章

1 动态规划法求解过程：

2图问题中的动态规划法

3组合问题中的动态规划法

第七章

1图问题中的贪心法

​编辑

第八章

1图问题中的回溯法

第九章

1分支限界法和回溯法的区别：

2 图问题中的分支限界法

3组合问题中的分支限界法

第十章

1问题的分类

2解决NP完全问题的方法

第十一章

第十二章

1 舍伍德型概率算法

2蒙特卡罗型概率算法

3 拉斯维加斯型概率算法

---

第一章

1 算法及其重要特性

算法：算法是对特定问题求解步骤的一种描述，是指令的有限序列

五个重要特性：输入、输出、有穷性、确定性、可行性。

2 算法的描述方法

自然语言、流程图、程序设计语言、伪代码。

第二章

1 算法的时间复杂性分析

概念：

时间复杂性也被称为时间复杂度；用于衡量算法运行效率的函数是一个关键指标。

渐近时间复杂度上界：假设存在两个正常数c和n₀，在所有情况下当n≥n₀