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.
304
第
11
章
新兴算法
前面章节讲述的都是用于解决常见问题的算法。显然，在你的编程生涯中，你会遇到一
些不在常见类别范畴之内的特殊问题。本章将介绍四种不同的
算法
来解决这些问题。
另一个不同在于本章将会着重关注随机性和概率两方面的内容。在前面的内容中，我们
使用随机和概率方法来分析算法在平均情况下的表现，这里的随机性则是本章算法中非
常重要的部分。实际上我们可以看到，相比确定性算法，概率算法将会是一个更有趣的
选择。在使用概率算法时，对于同样的输入同样的实现，运行两次的结果可能不一样。
而且有时我们会容忍错误的发生，即便算法“声称”无解。
11.1 特定情形下的衍生算法
本书之前提到的所有算法都是运行在一台确定的有限状态自动机上，因此这些算法能够
给出确定的答案。让我们来考虑一下放松一些限制将会产生的算法：
近似算法
与其寻找一个准确的答案，我们也可以接受一个并不完美的解。
并行算法
与其仅限在一台机器上串行执行算法，我们可以在多台机器上同时计算子问题。
概率算法
对于一个问题实例，与其每次都得到相同的结果，我们可以结合随机和近似思想来
计算结果，这样经过多次计算后，这些结果就能趋向于正确结果。
11.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,
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.