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.
算法基础
｜
47
算法基础
因此这个
while
循环最多运行
n
次。于是，
while
循环的时间约为
O
(
n
)
。综上所述，整
个算法的时间复杂度是
O
(
n
log
n
)
，因为排序的时间复杂度最大。
3.6 常用方法
本节将会介绍本书中用到的一些基本算法。要理解算法如何一步步解决具体问题，了解
这些策略是非常有必要的。第
10
章额外介绍了一些不太常见的方法，例如如何找到近
似解，或者使用大量随机尝试而不是穷尽搜索来求解。
3.6.1 贪心
对于一个规模为
n
个单位的问题，可以使用贪心算法分步解决。每一步，贪心算法都会
根据当前能够得到的信息做出最优解，这样可以让问题的规模下降
1
个单位。一旦
n
个
步骤全部完成，算法就可以返回计算出的结果。
例如，对包含
n
个数的数组
A
进行排序，贪心
选择排序
就是找到
A
[0,
n
－
1]
中最大的值，
然后和
A
[
n
－
1]
交换。接着重复这个过程，寻找
A
[0,
n
－
2]
中最大的值，然后和
A
[
n
－
2]
交换。这个过程会持续到整个数组排序完成。第
4
章介绍了关于这个算法的更多细节。
贪心算法在减小问题规模上其实是比较慢的。当每一步需要
O
(log
n
)
的时间时，贪心算
法将会有
O
(
n
log
n
)
的时间复杂度。如果每一步的时间复杂度是
O
(
n
)
，例如上文提到的
选择排序
，那么总体的时间复杂度将会是
O
(
n
2
)
。
3.6.2 分治
分治通常是将一个规模为
n
的问题划分成两个独立的子问题，其中每个子问题的规模约
为
n
/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.