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.
34
｜
第
2
章
也就是
O
(
n
2
)
。分析
ModGCD
算法的最坏情况有些难度，研究表明当
ModGCD
处理两
个连续的
Fibonacci
数字时性能最差。从图
2-5
上也可以推断出算法是平方级的，因为算
法性能在数据规模翻倍后变为原先的
4
倍。
计算最大公约数还有着更为优秀的算法，不过这些算法主要针对特别大的整数，因而在
实际场景中并不实用。
2.4.8 指数级算法性能
考虑有一种锁，它由
3
个连续的数字拨盘组成，每个拨盘包含
0~9
的数字，并且都可以
独立设置
10
个数字中的一个。假如你发现了这种锁，并且没有能将其打开的数字组合。
你可能认为这不过是耗费一些体力工作的问题，只要尝试从
000~999
的
1000
种组合中
可能的每一种即可。为了归纳这个问题，假定锁有
n
个表盘，那么总的可能性总数为
10
n
。用穷举方法解决这个问题被认为是指数级性能或者
O
(10
n
)
，这个例子以
10
作为基数，
但是更常见的指数底数一般是
2
。不过，对于任意的基数
b
（
b
> 1
）
,
它们的性能都是指
数级。
指数级算法仅仅对于一些非常小的
n
值较为实用。某些算法虽然最坏情况下的性能是指
数级，但是它们在平均情况下性能表现良好，因此在实际情况中仍然被大量使用。使用
单纯性
（
simplex
）算法解决线性规划问题就是一个很好的例子。
2.4.9 渐进增长小结
不论实际常数是大是小，拥有较好渐进增长的算法
最终
会比较差渐进
增长
的算法执行
得更快。真正区分两类算法的性能的转折点会根据实际常量的不同而有所不同，这里
的常量是实际存在的并且可以根据经验预估得出。此外，在渐近线分析时
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.