知识卡片

普通读书笔记卡 · 1708.b.3.o · 生成模型:未记录

渐近上界与紧确阶不同

理解等级:中级

若存在常数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)能够比我们已经使用