知识卡片

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

大O给出渐近上界

理解等级:中级

对非负成本函数,f(n)=O(g(n))表示存在固定正常数c与阈值n₀,使所有n≥n₀都有f(n)≤c·g(n)。c和阈值在比较中先选定,不能随每个n任意调整。

它只给足够大规模时的一个上界,不承诺紧确,也不自带最佳/平均/最坏标签;需先说明f代表哪种成本。比如线性函数也属于O(n²),因此仅说“大O是n²”不能反推实际必为平方增长。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      f(n)≤cg(n)。 通常我们以函数所处理的数据量来表示算法的性能。也就是说,对于大小为n的数据,我们用函数f(n)来表示它的算法性能。在很多情况下,我们可以完全确定f的具体值,但通常我们不需要关注此具体值。我们需要关注的是当算法处理的数据量变得无穷大时,算法的性能将趋近一个什么样的值。一个算法的

    参考来源

    - 位置:《算法精解:C语言描述》第4章《O表示法》(spine1199;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1167.html;u042-ch04-003)。 - 结论依据:42开头定义、增长率解释与正常数/阈值条件完整实读;以固定量词精化原文“对于常数c”的含混说法,上界不等于紧界是定义的直接边界。 - 原始内容:f(n)≤cg(n)。 通常我们以函数所处理的数据量来表示算法的性能。也就是说,对于大小为n的数据,我们用函数f(n)来表示它的算法性能。在很多情况下,我们可以完全确定f的具体值,但通常我们不需要关注此具体值。我们需要关注的是当算法处理的数据量变得无穷大时,算法的性能将趋近一个什么样的值。一个算法的