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.
算法的数学原理
｜
31
算法的
数学原理
ױ݆Ⴀీ
ኴႜ้क़0ms
o
!>!ຕ࿋܈
图 2-4：比较 mult 和 times
如图
2-4
所示，虽然
times
衍生算法的速度是
mult
算法的
1/2
，但是
times
和
mult
展
现了相同的渐近性能。
mult
2
n
/
mult
n
的比率大约是
4
，这证明了乘法的性能是平方级的。
我们定义
t
(
n
)
表示乘法算法在输入规模为
n
时的实际执行时间。根据这个定义，对于所
有的
n
>
n
0
来说，必然存在某些常数
c
（
c
> 0
），满足
t
(
n
)
≤
c*n
2
。我们不需要知道
c
和
n
0
的实际值是多少，只需要知道它们必然存在即可。这个
mult
算法实现在我们的平
台上执行时，常数
c
为
1/7
，
n
0
为
16
。
需要再次说明的是，修改算法实现来提升效率并不会改变算法是平方级性能的事实。尽
管如此，还是有其他的算法（
Zuras
，
1994
）可以让
n
位数相乘的明显速度快于平方级。
对于像数据加密这种需要频繁实现大数乘法的应用，这类算法非常重要。
2.4.7 性能不明显的计算
在很多情况下，仅仅通过算法的描述（如
加法
和
乘法
）就可以分辨出算法的性能是线性
级还是平方级的。例如，平方级的主要特征是嵌入的循环结构。但是，这样的直接分析
对某些算法却无法使用。例
2-5
给出了
GCD
算法，该算法是由欧几里德设计，用于计算
两个整数的最大公约数。
例
2-5
：欧几里得
GCD
算法
public static void gcd (int a[], int b[], int gcd[]) {
if (isZero (a)) {
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.