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 版)
331
附录
A
基准测试
本书为所有算法都提供了详细的性能数据因为性能数据的准确程度与基准测试
benchmarking
)的正确使用息息相关,我们在附录
A
中提供了一整套如何进行性能评
估的方法,这有助于消除读者对这些算法的有效性所可能持有的质疑。此外,我们还会
解释实验数据的精确计算方法,以便验证结果和理解算法在使用上的一些假设条件。
分析算法的方法有很多种。第
2
介绍了一种正式的理论的处理方法,包括最坏情况
和平均情况下的性能分析。我们可以根据这些结果做一些经验上的判断。例如,考虑
20
个数进行排序的性能,这
20
个数可以有
2.43
×
10
18
种排列,但是我们不可能枚举所
有排列情况,也不可能对这些排列一一排序再去计算算法的总体平均性能。因此,只能
依靠统计方法来正确计算出算法的期望性能。
统计基础
这里主要关注评估算法性能的几个关键点。感兴趣的读者可以参考任意一本统计学教材
来获取更多关于统计学方面的知识。
我们构建了
一套
独立的
实验
T
来计算算法的性能每次实验都特意将算法运行在规模
n
的数据集上。有时我们会做一些额外的工作来确保这些实验对于算法而言都是相对
等价的。不仅如此,这些实验还需要相互独立并且互不相同,以便更好地量化
不同
的算
法实现带来的性能差异。考虑到计算大量独立的等价实验的费用非常巨大,因此选择若
干次独立实验也是一个不错的选择。
实验集运行的结果会精确到毫秒。在使用
Java
编写代码时,我们会在算法运行前预先调
用系统的垃圾回收器,尽管这么做仍无法避免垃圾回收器可能在实验进行中运行,但能
够尽可能地减少和算法运行无关的时间花费。此外,我们会将最好的和最坏的结果当作 ...
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