《算法设计与分析》考试内容摘要
本文总结了《算法设计与分析》考试内容的主要知识点，涵盖了算法的定义、性质、时间和空间复杂性，初等操作、算法分析的目的、时间复杂性的评价方法等概念。同时，本文还涉及到堆的定义和性质、递归算法、分治法、贪婪法和克鲁斯卡尔算法等重要算法思想和方法。
一、算法的定义和性质
* 算法是解某一特定问题的一组有穷规则的集合。
* 算法具有有限性、确定性、输入、输出、能行性等性质。
二、算法的时间和空间复杂性
* 算法的时间复杂性越高，算法的执行时间越长；反之，执行时间越短。
* 算法的空间复杂性越高，算法所需的存储空间越多；反之越少。
* 算法的时间复杂性与问题的规模相关，是问题大小 n 的函数。
三、初等操作
* 所有的操作都具有相同的固定字长。
* 所有的操作的时间花费都是一个常数时间间隔。
四、算法分析的目的
* 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出更好的算法。
五、时间复杂性的评价方法
* 使用 T(n)的数量级（阶）评价算法的时间复杂性。
* 设算法 T(n)* 执行时间为 T（n），如果存在 T(n)*，使得lim T(n)−= 0T(n)n→∞ 就称 T(n)* 为算法的渐进时间复杂性。
六、堆的定义和性质
* 堆可以看做是一课完全二叉树。
* 堆具有所有叶节点不是处于第 d 层，就是处于 d-1 层的性质。
七、递归算法
* 递归算法是指算法自己调用自己，相应的算法称为递归算法。
* 递归分类：直接递归与间接递归。
* 递归本质：对原问题的求解可转化为对其性质相同的子问题的求解。
八、分治法
* 分治法就是把问题划分成多个子问题来进行处理，这些子问题互相独立，在结构上和原来的问题一样，但在规模上比原来的小。
九、贪婪法
* 贪婪法解决问题时，并不能保证它能找到最优解。
* 贪婪法设计思想：类似于登山法，一步步向前推进，从某一个初始状态出发，根据当前局部最优而不是全局最优策略，以满足约束条件，使目标函数的值增加最快或者最慢为准则，选择一个能够最快达到要求的输入元素，以便尽快构成问题的可行解。
十、克鲁斯卡尔算法和普里姆算法
* 克鲁斯卡尔算法算法思想：避环法。
* 普里姆算法算法思想：类似于求最短路径的狄斯奎诺算法。
