Skip to Main Content
算法技术手册(原书第2 版)
book

算法技术手册(原书第2 版)

by George T.Heineman, Gary Pollice, Stanley Selkow
August 2017
Intermediate to advanced content levelIntermediate to advanced
360 pages
8h 35m
Chinese
China Machine Press
Content preview from 算法技术手册(原书第2 版)
算法的数学原理
21
算法的
数学原理
巨大的变化。对于一个给定的程序和一个给定的值,最坏执行时间就是处理所有规模
n
的数据所需要的最长执行时间。
之所以关注算法的最坏情况,是因为它通常是最容易分析的情况。此外,它还能够说明
程序在各种场景下到底会有多慢。
更正式地说,如果
S
n
是所有规模为
n
的问题样本
s
i
构成的集合,
t
()
代表算法对于每一
个问题样本所需要的执行时间,那么算法在最坏情况下的执行时间为:
t
(
s
i
)
对于所有
s
i
S
n
的最大值。我们将
S
n
最坏情况的性能记
T
wc
(
n
)
T
wc
(
n
)
的增长率定义了算
法在最坏情况下的复杂度。
一般来说,通过计算每一份数据
s
i
来判定
算法在哪份数据上表现最坏,这种做法是不切
实际的——没有足够的资源。相反,算法分析人员会精心设计出能让算法的性能落入最
坏情况的问题样本。
2.3.2 平均情况
考虑设计一个支持
n
个电话的电话系统,其中
n
是一个非常大的数——要求在最坏情况
下,系统必须能够完成
n/
2
位用户同时呼叫另外
n/
2
位用户。虽然这个系统永远不会由
于过载而崩溃,但构造它还是需要花费很高的代价。因为现实生活中,
n/
2
位用户同时
呼叫另外
n/
2
位用户发生的概率极小。相反,我们可以设计一个非常容易构建的系统,
并借助数学工具来计算由载导致的系统崩溃的概率。
对于规模为
n
的样本集合,我们用一个概率分布
Pr
{
s
i
}
表示样本分布的概率。其中,单
个样本的出现概率为
0
1
,所有样本的概率的和为
1
。更加正式一点的定义为,如果
S
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.
Start your free trial

You might also like

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

Aurélien Géron
Go语言编程

Go语言编程

威廉·肯尼迪
C++语言导学(原书第2版)

C++语言导学(原书第2版)

本贾尼 斯特劳斯特鲁普

Publisher Resources

ISBN: 9787111562221