知识卡片

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

渐近上下界与紧界

理解等级:中级

O(g) 表示增长率的渐近上界,Ω(g) 是下界;同一函数同时属于两者才可称 Θ(g)。

证明时须找常数和阈值 n₀,使不等式对所有 n≥n₀ 成立。

O(n⁴) 可以描述 n³ 函数,但不是其紧界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

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