数据结构与算法经典问题解析--第一、二章

第一章：算法复杂度

三种渐进表示法：

• 大 O 表示法：定义严格的上界（最坏情况）
• Ω 表示法：定义严格的下界（最好情况）
• Θ 表示法：上界和下界相同时，可看作平均运行时间

第二章：递归与回溯

递归：任何调用自身的函数。

递归应用

• 斐波那契数列、阶乘
• 归并排序、快速排序
• 二分查找
• 树的遍历（中序、前序、后序）
• 图的遍历（DFS、BFS）
• 动态规划
• 分治算法
• 汉诺塔
• 回溯算法

回溯

一种采用分治策略进行穷举搜索的方法。应用：

• 生成所有二进制串 / k 进制串
• 背包问题
• 哈密顿回路
• 图着色问题