常数见证:把“同阶”钉牢
渐近界不是两条曲线看起来相近,而是存在固定常数,使不等式从某个阈值起对整个尾部成立。
0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n)要求存在 c₁>0、c₂>0、n₀,使每个 n≥n₀ 都满足。
阈值之后的夹轨
解析尾部成立定义判定 · 全部尾部
成立:这一组常数是 Θ 见证。
有限取样 · 仅作检查
取样通过不能推出对所有 n≥n₀ 成立;解析条件才对应定义。
即时判断
某组 c₁、c₂、n₀ 在 n=n₀ 到 1000 的每个整数上都通过。能否仅凭这些取样断定 f(n)=Θ(g(n))?