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.
20
｜
第
2
章
对于许多问题来说，单一的最优算法并不存在。选择一个算法需要对问题有着充分的理
解，并且知道这个问题将要处理数据规模的概率分布情况，此外还必须考虑算法的实际
行为。
这里提供了一些指导性的信息。算法通常可以按以下三类情况进行分析：
最坏情况
最坏情况是指算法对于一类问题样本表现出的最坏性能。通常，算法设计人员在描
述最坏情况时，会指出导致算法无法高效执行的输入数据的
特征
，而并非找出特定
的输入数据。
平均情况
平均情况是指算法在随机给定的数据上期望的执行情况。某些问题样本可能会由于
一些特例而导致程序需要更长的时间才能完成，但是大多数情况都并非如此。平均
情况描述了一般用户对算法性能的期望。
最好情况
最好情况是指算法对于一类问题样本表现出的最好性能。对于这类样本，算法只需
要执行很少的计算。在实际情况中，最好情况很少出现。
通过了解算法在每种情况下的性能，读者就能判断它是否适用于特定场景。
ৎຼᆶႾಇຕLjഄዐ205ڦᇮ໎
ໜऐݴքሞኟඓ࿋ዃਐྺ5ڦ࿋ዃฉ
ኴႜ้क़DŽڇ࿋ǖµsDž
ຕࡀఇ
o
ಇႾ໙݆2
ಇႾ໙݆3
ಇႾ໙݆4
ಇႾ໙݆5
图 2-3：第四种排序算法在处理几乎有序的数据时性能最好
2.3.1 最坏情况
对于任一特定值
n
，算法或者程序在处理所有规模为
n
的样本时的执行时间可能会发生
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.