2020算法复习题详解：多项式与非多项式时间复杂度

在2019-2020年的算法复习资料中，本章节涵盖了算法基础概念、算法特性及描述方法、特定算法（如欧几里得算法）的理解与实现、算法分类、复杂度分析以及常见算法种类。以下是重点知识点的详细阐述： 1. **算法基础**： - 算法定义：算法是一类问题的解决方法，它规定了求解问题的步骤和规则，确保在有限时间内得出结果。 2. **算法特性**： - **输入与输出**：算法接收输入数据并产生输出结果。 - **确定性**：每一步操作都有明确的规定，避免歧义。 - **可行性**：算法可以由有限步骤完成，不涉及无限循环或不可能的操作。 - **有穷性**：算法的执行不会无休止地进行。 3. **描述算法的方法**： - 自然语言：直观易懂但不够精确。 - 流程图：图形化表示算法步骤。 - 伪代码：半形式化的语言，结合自然语言和程序结构。 - 程序设计语言：实际编写代码实现算法。 4. **欧几里得算法（辗转相除法）**： - 递归或迭代实现，用于计算两个整数的最大公约数（GCD）。 5. **算法种类**： - 精确算法：精确求解问题，如欧几里得算法。 - 启发式算法：非精确但寻找有效解，如搜索算法。 - 近似算法：找到接近最优解的解决方案。 - 概率算法：利用随机性求解问题。 6. **数学归纳法**：用于证明算法的正确性，是算法理论中的重要工具。 7. **算法复杂度**： - 时间复杂度：衡量算法运行所需时间，包括最好、最坏和平均情况。 - 空间复杂度：算法所需的存储空间。 - 常见复杂度类别：如多项式时间（O(n), O(nlogn), O(n^2)等）和指数时间（O(2^n), O(n!)等）。 8. **好算法的标准**： - 正确性：正确解决问题。 - 简明性：简洁清晰的代码或描述。 - 效率：执行速度快。 - 最优性：在最坏情况下能达到最好时间复杂度。 9. **影响程序运行的因素**： - 算法设计、问题规模和输入数据。 - 计算机硬件性能。 10. **具体题目示例**： - 欧几里得算法的应用（求最大公约数）。 - 算法确定性和能行性的定义。 - 分析程序段的渐近时间复杂度。 通过这些知识点，学习者可以深入理解算法的基础理论和实践应用，为算法设计、分析和优化打下坚实基础。同时，理解算法复杂度有助于评估不同算法的效率，并在实际编程中做出合适的选择。