Figure 0.2 Which running time is better?
1 2 3 4 5 6 7 8 9 10
0
10
20
30
40
50
60
70
80
90
100
n
2n+20
n
2
Now another algorithm comes along, one that uses f
3
(n) = n + 1 steps. Is this better
than f
2
? Certainly, but only by a constant factor. The discrepancy between f
2
and f
3
is tiny
compared to the huge gap between f
1
and f
2
. In order to stay focused on the big picture, we
treat functions as equivalent if they differ only by multiplicative constants.
Returning to the definition of big-O, we see that f
2
= O(f
3
):
f
2
(n)
f
3
(n)
=
2n + 20
n + 1
≤ 20,
and of course f
3
= O(f
2
), this time with c = 1.
Just as O(·) is an analog of ≤, we can also define analogs of ≥ and = as follows:
f = Ω(g) means g = O(f )
f = Θ(g) means f = O(g) and f = Ω(g).
In the preceding example, f
2
= Θ(f
3
) and f
1
= Ω(f
3
).
Big-O notation lets us focus on the big picture. When faced with a complicated function
like 3n
2
+ 4n + 5, we just replace it with O(f(n)), where f(n) is as simple as possible. In this
particular example we’d use O(n
2
), because the quadratic portion of the sum dominates the
rest. Here are some commonsense rules that help simplify functions by omitting dominated
terms:
1. Multiplicative constants can be omitted: 14n
2
becomes n
2
.
2. n
a
dominates n
b
if a > b: for instance, n
2
dominates n.
3. Any exponential dominates any polynomial: 3
n
dominates n
5
(it even dominates 2
n
).
16
剩余317页未读，继续阅读
z_p_liu363912650
- 粉丝: 4
- 资源: 30
我的内容管理
展开
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述：模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成：理论与算法
- 基于语义元的相似度计算方法研究：改进与有效性验证
- 网格梯度多密度聚类算法：去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型：有效提升系统状态预测
- 煤矿安全评价：信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN：统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
