算法基础精要：分治、动态规划与贪心策略

"本资源是一份2018年秋季的算法基础知识笔记，涵盖了分治法、循环不变式、稳定排序算法、多优先级排序、选择算法、动态规划、贪心算法及其证明思路，以及摊还分析等核心概念。笔记强调理解和应用算法思维，如分治法中的合理划分和动态规划的最优子结构特征。" 1. **分治法**： 分治法是一种策略，将复杂问题分解成较小的相似子问题，分别解决后再合并结果。例如，大整数乘法和Strassen矩阵乘法就是分治法的应用。在适用分治法时，需确保在合并子问题时能节省时间，以保证效率。 2. **循环不变式**： 循环不变式是循环控制的关键，包括初始化、保持和终止三个阶段。在循环开始前为真，在每次循环迭代后保持为真，且当循环结束时，该不变式揭示了循环的结果。 3. **稳定排序算法**： 稳定排序算法保证相同元素的相对顺序在排序后不变。例如，冒泡排序和插入排序是稳定的。在某些场景下，如多优先级排序，稳定排序可以确保低优先级的元素不会因排序而排在高优先级元素前面。 4. **多优先级排序**： 在多优先级排序中，低优先级的元素先进行排序，允许被高优先级的元素打乱顺序。这种策略通常用于处理具有多个分类标准的数据。 5. **最坏时间复杂度为线性的时间选择算法**： 这类算法在最坏情况下仍能保证O(n)的时间复杂度，例如快速选择算法，通过分治策略和相对平衡的划分来实现。 6. **动态规划**： 动态规划是解决最优化问题的一种方法，通过构建最优子结构，自底向上计算最优值。这包括识别最优解的性质、写出动态规划方程、存储子问题的解，最后构造最优解。 7. **贪心算法**： 贪心算法通过每次做出局部最优选择来尝试达到全局最优。贪心选择性质证明需要比较贪心解与任何最优解，通过替换不同步的第一个元素并保持总价值不变，以证明贪心解的最优性。 8. **最优子结构性质与贪心选择性质的区别**： 最优子结构性质是指最优解的一个子集也是子问题的最优解，而贪心选择性质是指每次选择当前最优的解，最终得到整体最优解。 9. **摊还分析**： 摊还分析用于分析最坏情况下的平均性能，不依赖概率，能保证每个操作在多次运行后的平均性能。 10. **算法的作用**： 算法在解决问题时起着至关重要的作用，如排序、查找、优化等，是计算机科学的基础。 这些知识点构成了算法基础的核心，对于学习和理解算法设计和分析至关重要。通过深入理解和应用这些概念，可以解决更复杂的计算问题。