知识卡片

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

渐近比较不一定能排序任意两函数

理解等级:高级

渐近比较具有传递性,O 与 Ω 可互换方向;但它没有实数比较的三歧性。

若两函数的相对增长反复震荡,可能既无 f=O(g),也无 f=Ω(g),不能强行给它们排一个固定增长顺序。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 3 章 3.2 节“Comparing functions”(`OEBPS/chapter003.xhtml`)。 - 结论依据:原文列出传递、对称与转置对称,并以振荡指数函数说明三歧性不成立。 - 原始内容:Although any two real numbers can be compared, not all functions are asymptotically comparable.