算法导论笔记：伪代码、分治与概率分析

《算法导论笔记》是一份针对2019年面试准备的资料，主要聚焦于Thomas H. Cormen等作者编写的经典教材《算法导论》第三版。这份笔记详尽地涵盖了算法的基础概念，从伪代码的运用、算法的正确性证明及复杂度分析，到具体的排序算法如插入排序及其循环不变式。 在第二章中，重点介绍了插入排序算法，它是一种原址排序算法，通过将元素逐个插入已排序的部分来达到排序的目的。循环不变式是证明算法正确性的重要工具，对于插入排序，其不变式表明左侧数据总是有序的。分析算法的资源需求，包括计算机中的常见指令，如算术、数据移动和控制指令，它们的时间复杂性通常认为是常量时间。此外，作者强调了问题规模的不同度量标准，如排序算法以数组大小衡量，而乘法则根据数据的二进制位数。 分治法是后续章节的核心，它将大问题分解为规模较小的子问题，通过递归解决并合并结果。以归并排序为例，通过维持子数组A[pk-1]有序的状态，递归地将子问题解决，最后通过合并操作得到原问题的解答。递归算法的时间复杂度可以用递归式表示，例如对于分治问题，当子问题规模缩小至原问题的1/b时，时间复杂度可以进一步分析。 第四章深入探讨了分治策略的应用，如最大子数组问题和矩阵乘法。尽管简单的分治策略在某些情况下不如直接方法高效，但Strassen算法展示了分治在某些特定问题上的优化，比如将矩阵乘法的时间复杂度从8次降低到7次。 第五章转向概率分析与随机算法，引入了一个实际问题作为背景：在面试过程中招聘决策带来的费用估算。通过概率分析，考虑最坏情况下的费用，即面试者质量递增但成本最高的情况，同时指出现实中的面试者质量并非总是按固定顺序出现。 《算法导论笔记》提供了丰富的理论和实例，帮助读者理解算法设计的关键概念，以及如何通过分治、概率分析等策略优化算法性能。这份笔记对于准备面试的候选人来说，是深入理解算法原理和应用的宝贵资源。