1运行时间必须绑定模型与规模
闭卷重建运行时间必须绑定模型与规模的对象、状态、事件、不变量与一个失败反例。
理论计算：自动机、可计算性与复杂性 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2大O、大Ω与大Θ的量词
闭卷重建大O、大Ω与大Θ的量词的对象、状态、事件、不变量与一个失败反例。
3P与多项式鲁棒性
闭卷重建P与多项式鲁棒性的对象、状态、事件、不变量与一个失败反例。
4空间复杂度与配置数
闭卷重建空间复杂度与配置数的对象、状态、事件、不变量与一个失败反例。
5层次定理与资源增加
闭卷重建层次定理与资源增加的对象、状态、事件、不变量与一个失败反例。
6实验：渐近增长比较
闭卷重建实验：渐近增长比较的对象、状态、事件、不变量与一个失败反例。
7实验：配置数上界计算
闭卷重建实验：配置数上界计算的对象、状态、事件、不变量与一个失败反例。
第 1 页 · 背面（答案）
核心机制：渐近上界、下界和紧确界都有阈值n0与正常数，忽略低阶项需要给量词证明；实验入口：用定义证明3n²+5n+7属于Θ(n²)，明确选择常数和阈值；边界：O不是等号也不是平均值；一组测量曲线不能证明渐近下界。
核心机制：时间复杂度是最坏或其他指定口径下步数关于编码长度n的函数，模型差异需用模拟定理连接；实验入口：分别按单带TM和RAM模型分析字符串扫描，写清一步操作与输入长度；边界：不能把数值大小当输入长度；二进制整数N的编码长度是Θ(log N)。
核心机制：空间度量工作带使用格数，时间上界可由配置数与防止重复配置得到联系；实验入口：计算使用s(n)空间的确定机配置编码字段与数量上界；边界：输入带是否计入空间必须按模型声明；递归深度与每帧空间应相乘。
核心机制：P包含确定性多项式时间可判定语言，在合理确定模型间通常保持多项式差距；实验入口：把多项式子程序组合、循环和编码转换逐项估算；边界：多项式次数很高未必实用，而指数算法对小实例也可能可用；类别不等于工程速度。
核心机制：对给定n计算多项式与指数工作量并输出首次超过预算的n，使用整数避免浮点误判；实验入口：覆盖小预算、边界恰等、不同次数和无可行值；边界：有限阈值实验不能证明渐近类别，只帮助理解增长速度。
核心机制：在可构造资源界下，更多时间或空间严格增加可判定语言能力，证明使用对角模拟和编码开销；实验入口：梳理时间层次证明中通用模拟器、时钟和对角翻转三件事；边界：不能把P是否等于NP当作层次定理直接推论，条件和模型不同。
核心机制：输入状态数、带字母数和空间格数，计算简化单带配置数上界；实验入口：测试零工作格、不同字母表和较大整数；边界：上界可能宽松；得到有限配置数并不自动给出最优时间界。