← 返回刚才阅读的位置

知识卡片

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

渐近式中的等号不是普通等号

理解等级:高级

写 f(n)=O(g(n)) 时,等号通常表示集合成员关系;写 2n²+Θ(n) 时,Θ(n) 代表一个未命名的函数。

链式渐近等式是逐步丢弃细节,不能按普通等式任意反向替换。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第3章 运行时间的刻画 · 查看原书依据

      When the asymptotic notation stands alone (that is, not within a larger formula) on the right-hand side of an equation (or inequality), as in 4n2 + 100n + 500 = O(n2), the equal sign means set membership: 4n2 + 100n + 500 ∈ O(n2). In general, however, when asymptotic notation appears in a formula, we interpret it as standing for some anonymous function that we do not care to name.

    参考来源

    - 位置:《算法导论(第4版)》第 3 章 3.2 节“Asymptotic notation in equations and inequalities”(`OEBPS/chapter003.xhtml`)。 - 结论依据:第3章说明独立渐近记号右项的等号表示集合成员关系;公式内的渐近记号指代匿名函数,故不能按普通等号任意反向替换。 - 原始内容:When the asymptotic notation stands alone (that is, not within a larger formula) on the right-hand side of an equation (or inequality), as in 4 n 2 + 100 n + 500 = O ( n 2 ), the equal sign means set membership: 4 n 2 + 100 n + 500 ∈ O ( n 2 ). In general, however, when asymptotic notation appears in a formula, we interpret it as standing for some anonymous function that we do not care to name.