C01 · 第 5 章 · 课程规划页
渐近复杂度、归约与可计算性
本章研究渐近复杂度、归约与可计算性。内容依次处理渐近上界、下界与摊还分析、多项式归约、NP 完全性与验证器、停机问题、不可判定性与可计算边界。
- 所在 Part
- 第三编 复杂度与综合复习
- 预计学习
- 40 分钟
- 建设状态
- 已规划，尚无正式正文
计划实验
本章未登记独立交互实验；定义、公式和例题仍按下列提纲规划。
LEARNING OBJECTIVES
完成本章后应能
- 01准确说明渐近上界、下界与摊还分析。
- 02完成多项式归约、NP 完全性与验证器所需的推导、证明或算法。
- 03使用计算、例题或反例检验停机问题、不可判定性与可计算边界。
PLANNED SECTIONS
计划章节结构
- 01
渐近上界、下界与摊还分析
界定渐近上界、下界与摊还分析，明确使用的条件、主要结论与可复核步骤。
- 02
多项式归约、NP 完全性与验证器
推导多项式归约、NP 完全性与验证器，明确使用的条件、主要结论与可复核步骤。
- 03
停机问题、不可判定性与可计算边界
检验停机问题、不可判定性与可计算边界，明确使用的条件、主要结论与可复核步骤。
计划定义
渐近上界、下界与摊还分析：对象、记号与前提
围绕渐近上界、下界与摊还分析列出主要对象、符号、前提与定义边界。
计划公式
多项式归约、NP 完全性与验证器：关系、判据与可复核步骤
把多项式归约、NP 完全性与验证器整理为可检查的关系、判据或算法步骤；涉及定量模型时写出公式，并说明符号、适用条件，以及需要时的单位或复杂度。
计划例题
停机问题、不可判定性与可计算边界：案例、反例与核验
围绕停机问题、不可判定性与可计算边界给出明确输入、前提或数据，逐步分析并用反例、误差、守恒量或边界条件复核。
计划练习
渐近复杂度、归约与可计算性：定义、关系与边界综合练习
联结渐近上界、下界与摊还分析、多项式归约、NP 完全性与验证器与停机问题、不可判定性与可计算边界，分别检验定义辨析、主要步骤和适用边界。
本章概念落点
以下位置是术语、搜索和知识图谱引用本计划章节时使用的稳定链接。
- 算法复杂度用渐近记号比较算法随输入规模增长的时间和空间成本，并区分最坏与平均情况。
关键词
渐近复杂度、归约、可计算性、第三编 复杂度与综合复习、数据结构、算法与复杂度