August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
14
第
2
章
算法的数学原理
选择算法的一个很重要的考虑因素就是算法的执行速度。计算一个算法的期望执行时间
本质上是一个数学运算过程。本章将透过现象看本质，阐述隐藏在算法时间预测背后的
数学原理。在阅读本章之后，读者将能够理解本书中使用到的各类数学术语。这些术语
贯穿全书，也时常出现在其他算法类书籍当中。
2.1 问题样本的规模
问题样本是解决问题的程序所使用的特定输入数据集。在大部分问题中，随着这一数据
集规模的增长，程序的执行时间也在不断增加。同时，过度地对样本数据进行编码（可
能使用了压缩技术），可能会不必要地降低程序的执行效率。寻找一种最优的样本编码
方式是极其困难的，因为问题发生在复杂的现实世界，而且还需要进行合理的翻译才能
被程序求解。
在评估算法时，我们会尽量假定问题样本的编码并不是影响算法效率的决定性因素。问
题样本的表现方式应当仅仅依赖于待执行操作的类型。设计高效的算法通常从选择一个
合适的数据结构开始。
由于没法对问题样本给出正式定义，因此我们假设样本以一种简洁且可以普遍接受的方
式对样本进行编码。例如，当对
n
个数字进行排序时，根据惯例，我们会假定数字可以
存储在计算平台上
32
位的字长里，并且待排序的样本规模为
n
。假如某些数字需要用多
于
1
个字长的空间存储，例如某个固定数量的字长，那么在衡量样本空间时会多乘上一
个常量。
算法研究人员认为，即使给定编码方式，要精确计算出性能费用也是不切实际的。因此，
他们断言，如果一些算法的性能费用仅仅是常数倍的差异，那么它们可以被认为是
渐近
等价
的。换句话说，问题空间的不断增长所带来的算法性能差异是无关紧要的。 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.