通过局部最优解得到全局最优,但不一定最优,需证明贪心策略的正确性。
分治算法:通过递归将问题划分为相同或相似的子问题,典型例子二分查找、快速排序。需合并子问题解为原问题解,通常更高效。...5.图的搜索:BFS与DFS实现与应用场景对比,最短路径算法如Dijkstra算法与Floyd算法。
其他:哈希表的冲突解决方法、堆的实现与应用。...分治算法:通过递归将问题划分为相同或相似子问题,典型例子二分查找、快速排序。需合并子问题解为原问题解,通常更高效。
二分查找:在有序数组中查找目标值,每次比较中间元素,递归左区间或右区间。...递归调用 O(nlogn) 不稳定
归并排序:递归地拆分序列,合并有序子序列 O(nlogn) 稳定
最短路径:寻找图中两个节点之间的最短路径长度。Dijkstra算法与Floyd算法。...Dijkstra算法:从起点开始向外扩展,每次选取距离起点最近的未选定点,直到扩展到终点。适用于有向图。
Floyd算法:通过填充dpi表示i到j的最短路径,遍历所有点作为中间点更新最短路径。