知识卡片

普通读书笔记卡 · 5654.c.1.b

大O给上界而非精确阶

理解等级:中级

大O描述一种最终能覆盖被分析资源函数增长的上界:超过某个规模后,资源需求不超过参照函数的某个固定倍数。它允许宽松上界,不要求双方必定处在同一精确增长级别。

需要同时限定上下两侧时才讨论紧界。原书把上界解释成同级增长过强,且本EPUB公式符号有缺失;这里依据可读文字和已读图解释上界关系,不补造数学摘录。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      时间复杂度分析本质上是计算“操作数量 ”的渐近上界,它具有明确的数学定义。 函数渐近上界 ) ≤ ⋅ ( ) ( ) ) = ( ( )) 若存在正实数 和实数 ,使得对于所有的 ,均有 ,则可认为 给出了 的一个渐近上

    参考来源

    - 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[25959,26069)) - 结论依据:实际渐近上界段和图2-8支持,明确原文上界/同级混用与公式缺失。 - 原始内容:时间复杂度分析本质上是计算“操作数量 ”的渐近上界,它具有明确的数学定义。 函数渐近上界 ) ≤ ⋅ ( ) ( ) ) = ( ( )) 若存在正实数 和实数 ,使得对于所有的 ,均有 ,则可认为 给出了 的一个渐近上