知识卡片

普通读书笔记卡 · 3596.c.2

递归不等式只给单侧界

理解等级:中级

把递归运行时间写成“≤”只约束上界,应求 O 界;写成“≥”只约束下界,应求 Ω 界。

仅有一侧不等式不能直接宣称 Θ 界,除非再给出相匹配的另一侧证明。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 4 章“Conventions for recurrences”(`OEBPS/chapter004.xhtml`,文本字符 [5000, 10000))。 - 结论依据:原文分别说明上界不等式用 O、下界不等式用 Ω 表示。 - 原始内容:Because such a recurrence states only an upper bound on T ( n ), we express its solution using O -notation rather than Θ-notation.