知识卡片
渐近上下界与紧界
O(g) 表示增长率的渐近上界,Ω(g) 是下界;同一函数同时属于两者才可称 Θ(g)。
证明时须找常数和阈值 n₀,使不等式对所有 n≥n₀ 成立。
O(n⁴) 可以描述 n³ 函数,但不是其紧界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
- · 渐近上下界与紧界
原书出处 · 1 处
- 第3章 运行时间的刻画 · 查看原书依据
If you can show that a function is both O(f (n)) and Ω(f (n)) for some function f (n), then you have shown that the function is Θ(f (n)).
参考来源
- 位置:《算法导论(第4版)》第 3 章 3.1–3.2 节(`OEBPS/chapter003.xhtml`,图 3.2)。
- 结论依据:原文用多项式示例区分上、下和紧界,并给出 O 的常数与阈值定义;图 3.2 已核对。
- 原始内容:If you can show that a function is both O ( f ( n )) and Ω( f ( n )) for some function f ( n ), then you have shown that the function is Θ( f ( n )).