八、算法设计与分析：

常见算法：

回溯方法：

• 用深度优先的探索问题的解空间。
• 应用场景：N皇后问题。（背）

分支界限法：

• 用广度优先的探索问题的解空间，采用的是分支界限法算法设计策略。

分治法：

• 原问题分解若干子问题、把子问题求解、然后子问题解合并。
• 使用场景：归并排序法、快速排序法、最大子段和问题。
• 使用递归方法。
• Tips：会有重复的子问题。

贪心算法：

• 总是做出当前来说最好的选择，局部最优解。
• 最适合解决（应用场景）：部分背包问题、邻分（分数）背包、Dijkstra算法。

动态规划：

• 把所有子问题解记录表中，不用重复求子问题 ，以获取问题最优解为目标。
• 最适合解决（应用场景）：0-1背包问题、最长公共子序列、矩阵连乘。

0-1背包问题：

• 时间复杂度和空间复杂度均为O(nw)，- 其中n是物品数量，w是背包容量。

最长公共序列：

• 时间复杂度为O(n^2)

矩阵连乘：

• 时间复杂度为O(n^2)，空间复杂度为O(n^3)

算法小点：

• 完全二叉树适合采用顺序存储、一般二叉树适合采用链式存储。

• 静态查找：顺序~、折半~（二分~）、分块~。
• 动态查找：二叉排序树、平衡二叉树、B树、哈希表。