知识卡片
大O给出渐近上界
对非负成本函数,f(n)=O(g(n))表示存在固定正常数c与阈值n₀,使所有n≥n₀都有f(n)≤c·g(n)。c和阈值在比较中先选定,不能随每个n任意调整。
它只给足够大规模时的一个上界,不承诺紧确,也不自带最佳/平均/最坏标签;需先说明f代表哪种成本。比如线性函数也属于O(n²),因此仅说“大O是n²”不能反推实际必为平方增长。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 大O给出渐近上界
原书出处 · 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的具体值,但通常我们不需要关注此具体值。我们需要关注的是当算法处理的数据量变得无穷大时,算法的性能将趋近一个什么样的值。一个算法的