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页未读，继续阅读
DQZQ
- 粉丝: 11
- 资源: 19
我的内容管理
展开
最新资源
- C++多态实现机制详解：虚函数与早期绑定
- Java多线程与异常处理详解
- 校园导游系统：无向图实现最短路径探索
- SQL2005彻底删除指南：避免重装失败
- GTD时间管理法：提升效率与组织生活的关键
- Python进制转换全攻略：从10进制到16进制
- 商丘物流业区位优势探究：发展战略与机遇
- C语言实训：简单计算器程序设计
- Oracle SQL命令大全：用户管理、权限操作与查询
- Struts2配置详解与示例
- C#编程规范与最佳实践
- C语言面试常见问题解析
- 超声波测距技术详解：电路与程序设计
- 反激开关电源设计：UC3844与TL431优化稳压
- Cisco路由器配置全攻略
- SQLServer 2005 CTE递归教程：创建员工层级结构
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
