【算法设计与分析复习知识点】
1. **算法定义与特性**：算法是一系列明确的步骤，用于解决特定问题或执行特定任务。它必须满足五个基本特性：可行性、确定性、有限性、输入和输出。可行性指算法能被执行，确定性表示在给定条件下输出唯一，有限性意味着算法在有限步骤内结束，输入是算法处理的数据，输出则是处理后的结果。
2. **算法分析的两个阶段**：分析算法通常分为两个阶段：渐进分析和具体分析。渐进分析关注算法的运行时间或空间需求的增长趋势，主要用大O、Ω和Θ符号表示。具体分析则更关注算法在实际执行时的具体性能，例如精确的运行时间和空间占用。
3. **渐进符号的性质**：如果f1(n)=O(g1(n))且f2(n)=O(g2(n))，那么f1(n)+f2(n)=O(max{g1(n), g2(n)})，表示两个渐进上界的合并不会超过它们中较大的那个。
4. **Θ符号的性质**：若f1(n)=Θ(g1(n))且f2(n)=Θ(g2(n))，则f1(n)+f2(n)的复杂度可能是Θ(max{g1(n), g2(n)})，但并不总是如此，需要具体分析。
5. **证明|log2n|=O(n)**：随着n的增长，对数函数增长远慢于线性函数，因此|log2n|的增长速度比n小得多，所以|log2n|是n的渐进上界。
6. **证明3nlog2n=O(n^2)**：因为log2n相对于n是低阶项，所以3nlog2n的复杂度会随着n的增大而小于n^2。
7. **数学归纳法证明**：未给出具体的证明题目，但数学归纳法通常用于证明某个命题对所有自然数成立，分为基础步骤（验证n=1的情况）和归纳步骤（假设n=k时命题成立，证明n=k+1也成立）。
8. **递归关系式求解**：未提供具体关系，递归关系式的求解通常涉及公式解法、主定理的应用或转换成等比数列求解。
9. **递推关系式求解**：同样需要具体的关系式，递推关系的解通常通过特征根法、逐步展开或矩阵方法来解决。
10-11. **递推关系式求解**：未提供具体关系，解法与前面类似。
12. **分治法**：分治法包括分解问题、解决子问题和组合子问题。SPARKS语言描述的分治策略抽象控制可能包括递归调用、子问题的合并以及递归基的处理。
13. **二分检索的递归过程**：二分检索将区间不断减半直到找到目标或确定不存在，递归过程包括设置左、右边界，比较中间元素，根据比较结果调整搜索范围。
14. **三分检索算法**：该算法在二分的基础上增加了一个中间点，更快缩小查找范围，最坏情况下的时间复杂度为O(log3n)。
15. **二元树路径长度公式**：在二元树中，外部路径长度E加上内部路径长度I等于所有边的数量2n，即E+I=2n，所以E=2n-I，而内部结点数量I=n-1，代入得E=I+2n。
16. **比较为基础的算法时间下界**：基于比较的算法最坏时间下界通常是O(n log n)，如排序算法。
17. **线性存储有序表检索**：线性检索的最坏时间是O(n)，因为在最坏情况下需要检查所有元素。
18. **二次取中值规则**：在选择问题中，二次取中值规则是一种优化策略，通过取中间两个元素的平均值作为基准，减少分区不平衡。
19. **斯特拉森矩阵乘法**：斯特拉森算法通过7次较小的矩阵乘法实现2x2矩阵的乘法，其时间复杂度为O(n^log27)。
20. **手算证明矩阵乘法**：未给出具体公式，通常需要利用矩阵运算规则验证结果。
21. **归并排序的时间复杂度**：归并排序的最好情况是O(n log n)，因为总是将数组均分为两半。
22. **“由底向上”的归并排序**：这种排序避免了使用额外的栈空间，通过自底向上的合并步骤实现。
23. **约束条件、可行解、目标函数与最优解**：约束条件是问题的限制，可行解满足所有约束，目标函数是优化的目标，最优解是使目标函数达到极值的可行解。
24. **背包问题**：背包问题是一个优化问题，GREEDY-KNAPSACK贪心算法与最优解的关系取决于物品的权重和价值。
25. **0/1背包问题**：0/1背包问题要求每个物品只能取或不取，优化目标是在容量限制下最大化价值。
26. **贪心方法**：贪心方法每次做出局部最优选择，期望全局最优。在SPARKS语言中，可以通过递归或迭代实现贪婪策略。
27. **程序分布到磁带**：贪心策略可能导致非最优解，因为仅考虑当前选择而不顾及后续影响。
28. **算法5.4的解与作业处理时间定理**：算法5.4的解以及作业处理时间定理的证明需要具体算法细节。
29. **构建和调整min-堆**：min-堆的构造和调整算法包括插入新元素、删除最小元素和维护堆性质。
30. **树的度数与节点数关系**：在k元树中，所有内部节点度数为k，外部节点数n满足n mod (k-1)=1，存在这样的k元树。
31. **树的构造与度数证明**：可以构造满足特定度数条件的树，并证明内部节点的度数。
以上知识点涵盖了算法设计与分析的核心概念，包括算法分析、递归、分治法、排序、数据结构（如二元树和堆）、优化问题（如背包问题）以及贪心策略。
