东南大学算法设计与分析复习题

### 东南大学算法设计与分析复习题解析 #### 基本概念 1. **基本运算**：在解决特定问题时，占据主导地位的操作。它通常指算法中最频繁执行的操作，例如比较、加减乘除等。在评估算法效率时，我们主要关注这种基本运算的执行次数。 2. **算法的时间复杂性**：描述了算法运行时间随着输入数据规模（通常用n表示）变化的趋势。形式上，如果一个算法的基本操作次数可以用输入规模n的函数T(n)来表示，则T(n)即为该算法的时间复杂性。 3. **渐近时间复杂性**：当输入规模n趋向于无限大时，算法的时间复杂性的表现形式。这通常用来评估算法的长期性能。 4. **渐进时间复杂性的记号定义**： - **O-记号**（大O记号）：表示算法的上界，即算法执行时间不会超过某个常数倍的f(n)。形式化表示为T(n) = O(f(n))，意味着存在某个正数c和正整数n0，对于所有的n ≥ n0，都有T(n) ≤ c * f(n)。 - **Ω-记号**（大欧米伽记号）：表示算法的下界，即算法执行时间至少是某个常数倍的f(n)。形式化表示为T(n) = Ω(f(n))，意味着存在某个正数c和正整数n0，对于所有的n ≥ n0，存在无穷多个n，使得T(n) ≥ c * f(n)。 - **Θ-记号**（大西塔记号）：同时表示算法的上界和下界，即算法执行时间大致与f(n)成比例。形式化表示为T(n) = Θ(f(n))，意味着存在两个正数c1和c2及正整数n0，对于所有的n ≥ n0，都有c1 * f(n) ≤ T(n) ≤ c2 * f(n)。 5. **最坏情况时间复杂性**：在所有可能的输入中，算法需要执行的最大基本操作次数。这是评估算法性能的一个重要标准。 6. **平均情况时间复杂性**：所有可能输入情况下的平均基本操作次数。通常假定每个输入出现的概率相同。 7. **算法与计算过程**：算法是一组明确的指令集合，具有确定性、能行性、输入、输出和有穷性的特点。而计算过程是指一组指令，除了不满足有穷性外，其他四个特性都满足。 8. **算法研究的主要步骤**： - 设计：设计解决问题的算法。 - 表示：将算法以清晰的方式表示出来。 - 确认：确认算法是否能正确处理合法和非法输入。 - 分析：分析算法的时间复杂性和空间复杂性。 - 测试：通过测试确保算法的正确性和有效性。 9. **算法评价标准**： - 正确性：算法是否能正确解决问题。 - 健壮性：算法是否能优雅地处理异常情况。 - 简单性：算法的易理解程度。 - 高效性：算法的时间和空间效率。 - 最优性：算法是否达到理论上的最优效率。 10. **多项式时间和指数时间**：多项式时间算法是指那些执行时间随着输入规模n的增长呈多项式增长的算法，这些算法通常被认为是有效的。而指数时间算法的执行时间随着输入规模的增长呈指数增长，这类算法通常不适合处理大规模数据。 11. **相互独立的函数序列**：在数域上的一组函数{μ0(x), μ1(x), …, μn(x)}，如果对于任意的μk(x)，都不存在其他函数项线性组合而成μk(x)，那么这组函数序列被称为相互独立的。 12. **常系数线性递归方程的解**： - 当特征根互不相同时，解的形式为：\(an = A_1 + A_2 + \cdots + A_r\)。 - 当特征根为一对共轭复数时，解的部分形式为：\(Aρ^n\cos(nθ) + Bρ^n\sin(nθ)\)。 - 当特征根为多重根时，解的部分形式为：\(C_1α^n + C_2nα^n + \cdots + C_kn^{k-1}α^n\)。 - 对于非齐次方程，解的形式为齐次方程的通解加上非齐次方程的一个特解。 13. **求和与积分的关系**：在某些情况下，求和中的通项可以通过积分的方式来估计或求解。通过适当放大或缩小求和项，可以得到其上下界。 14. **主定理及其应用**：主定理用于分析分治算法的时间复杂性。基于不同的情况，可以得出不同形式的时间复杂性。通过主定理的应用，可以启发我们在设计算法时考虑如何合理分配子问题的大小，以达到最优或接近最优的时间复杂性。 通过以上知识点的总结，我们可以看出算法设计与分析涉及到了许多重要的概念和技术。了解这些基础概念对于深入理解和掌握算法至关重要。在实际应用中，这些概念和技术可以帮助我们更好地分析和优化算法，提高算法的效率和实用性。