16
Algorithms
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
disregard what happens for small values of n. For example, suppose we are choosing between
two algorithms for a particular computational task. One takes f
1
(n) = n
2
steps, while the
other takes f
2
(n) = 2n + 20 steps (Figure 0.2). Which is better? Well, this depends on the
value of n. For n ≤ 5, f
1
is smaller; thereafter, f
2
is the clear winner. In this case, f
2
scales
much better as n grows, and therefore it is superior.
This superiority is captured by the big-O notation: f
2
= O(f
1
), because
f
2
(n)
f
1
(n)
=
2n + 20
n
2
≤ 22
for all n; on the other hand, f
1
6= O(f
2
), since the ratio f
1
(n)/f
2
(n) = n
2
/(2n + 20) can get
arbitrarily large, and so no constant c will make the definition work.
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).
剩余335页未读，继续阅读
elessar_elessar
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- Lombok 快速入门与注解详解
- SpringSecurity实战：声明式安全控制框架解析
- XML基础教程：从数据传输到存储解析
- Matlab实现图像空间平移与镜像变换示例
- Python流程控制与运算符详解
- Python基础：类型转换与循环语句
- 辰科CD-6024-4控制器说明书：LED亮度调节与触发功能解析
- AE particular插件全面解析：英汉对照与关键参数
- Shell脚本实践：创建tar包、字符串累加与简易运算器
- TMS320F28335：浮点处理器与ADC详解
- 互联网基础与结构解析：从ARPANET到多层次ISP
- Redhat系统中构建与Windows共享的Samba服务器实战
- microPython编程指南：从入门到实践
- 数据结构实验：顺序构建并遍历链表
- NVIDIA TX2系统安装与恢复指南
- C语言实现贪吃蛇游戏基础代码
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
