知识卡片
渐近上界与紧确阶不同
若存在常数c>0和n₀,使充分大n时T(n)≤c·f(n),则T∈O(f)。若存在常数c′>0使T(n)≥c′·f(n),则T∈Ω(f);两者同时成立时T∈Θ(f)。这些关系需要指定输入规模、成本与所讨论的最好/最坏/平均情形。
线性算法也属于更宽松的O(2ⁿ),但该描述没有体现已知的线性上界;这不意味着O(2ⁿ)是精确分析的结果。原文把某些下界写成不带常数因子的g(n)≤t(n),应补上渐近常数与阈值。
大O不是默认等于Θ:获得上界不能自动获得匹配下界;作者在本书用O作简写时,具体结论仍需查看证明和前提。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
下界。一个能够计算出执行时间的上界(O)和下界(Ω)的算法,通常用Θ(f(n))来表示,其中f(n)是t(n)的上界O(f(n))以及下界的渐进表示。 为了简化分析和说明,我们选择一个比较不正式(但是被广泛接受和使用)的记法O(f(n))。我们保证讨论算法行为时,没有一个f'(n)能够比我们已经使用
参考来源
- 位置:《算法技术手册》第2章《最后一点》(spine1475;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1439.html;u040-ch02-016)。
- 结论依据:40全文O、Ω、Θ表述及加法例实读,按标准渐近定义补充常数和阈值。
- 原始内容:下界。一个能够计算出执行时间的上界(O)和下界(Ω)的算法,通常用Θ(f(n))来表示,其中f(n)是t(n)的上界O(f(n))以及下界的渐进表示。 为了简化分析和说明,我们选择一个比较不正式(但是被广泛接受和使用)的记法O(f(n))。我们保证讨论算法行为时,没有一个f'(n)能够比我们已经使用