知识卡片
小o与小ω的严格界
O(g) 允许同阶,o(g) 要求 f 相对 g 渐近可忽略:每个正倍数 c·g 最终都大于 f。
对应地,ω(g) 表示 f 最终超过 g 的任意正倍数。
故 2n=o(n²),但 2n² 不是 o(n²)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第3章 运行时间的刻画 · 查看原书依据
The main difference is that in f (n) = O(g(n)), the bound 0 ≤ f (n) ≤ cg(n) holds for some constant c > 0, but in f (n) = o(g(n)), the bound 0 ≤ f (n) < cg(n) holds for all constants c > 0.
参考来源
- 位置:《算法导论(第4版)》第 3 章 3.2 节“o-notation”与“ω-notation”(`OEBPS/chapter003.xhtml`,式中极限图片已核对)。
- 结论依据:原文分别给出全称常数与阈值的定义,并列举 2n 与 2n² 的对比。
- 原始内容:The main difference is that in f ( n ) = O ( g ( n )), the bound 0 ≤ f ( n ) ≤ cg ( n ) holds for some constant c > 0, but in f ( n ) = o ( g ( n )), the bound 0 ≤ f ( n ) < cg ( n ) holds for all constants c > 0.