知识卡片

普通读书笔记卡 · 1289.g.4.a

小o与小ω的严格界

理解等级:中级

O(g) 允许同阶,o(g) 要求 f 相对 g 渐近可忽略:每个正倍数 c·g 最终都大于 f。

对应地,ω(g) 表示 f 最终超过 g 的任意正倍数。

故 2n=o(n²),但 2n² 不是 o(n²)。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.