知识卡片
渐近式中的等号不是普通等号
写 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.