知识卡片

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

软大O忽略多项式对数因子

理解等级:中级

软大O记号允许在O(g(n))的界上额外乘以log^k n,其中k为常数;它只隐藏多项式对数因子,不能忽略任意多项式因子。

不同文献可能把对数作用于g(n),须核对定义。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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 }.