知识卡片
软大O忽略多项式对数因子
软大O记号允许在O(g(n))的界上额外乘以log^k n,其中k为常数;它只隐藏多项式对数因子,不能忽略任意多项式因子。
不同文献可能把对数作用于g(n),须核对定义。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第3章 运行时间的刻画 · 查看原书依据
there exist positive constants c, k, and n0 such that 0 ≤ f (n) ≤ cg(n) lgk(n) for all n ≥ n0}.
参考来源
- 位置:《算法导论(第4版)》第3章《运行时间的刻画》(OEBPS/chapter003.xhtml,文本字符[40000,45000))。
- 结论依据:问题3-6的 Art_P87 给出软大O集合定义,正文限制为常数次 lg n 因子;章注说明另有按 lg g(n) 定义的变体。图中符号已与 XHTML 核对。
- 原始内容:there exist positive constants c , k , and n 0 such that 0 ≤ f ( n ) ≤ cg ( n ) lg k ( n ) for all n ≥ n 0 }.