《算法技术手册》一2.3 最好、最坏和平均情况下的性能分析

简介: 本节书摘来华章计算机《算法技术手册》一书中的第2章 ,第2.3节, George T.Heineman Gary Pollice Stanley Selkow 著 杨晨 曹如进 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.3 最好、最坏和平均情况下的性能分析

也许有人会问,上述结果是否对于所有的输入问题样本都成立?第二种排序算法对于同等规模的其他数据样本表现会如何呢?
输入数据可能包含大量已排好序的元素。
输入数据可能包含重复值。
无论输入数据规模n是多少,元素集合都可以从一个非常小的数据集扩展而来,只不过会有相当多的重复值。
从图2-1上可以看出,第四种排序算法虽然在排序n个乱序字符串时最慢,但它在处理已经排好序的数据时却是最快的。不过,这种领先优势消失得非常快,如图2-2所示,在排序32个乱序的字符串时,第三种排序算法的性能最好。
2017_09_19_153908
图2-2:处理完全或者几乎有序的数据时,排序算法的性能
尽管如此,如果一个包含n个字符串的输入“近乎有序”,比如输入数组由有序数组中n/4的字符串(占总字符串的25%)与距离其4个位置的元素交换而得。那么,最终结果会有些出乎意料,如图2-3所示,第四种排序算法的性能表现要远远好于其他排序算法。
对于许多问题来说,单一的最优算法并不存在。选择一个算法需要对问题有着充分的理解,并且知道这个问题将要处理数据规模的概率分布情况,此外还必须考虑算法的实际行为。
这里提供了一些指导性的信息。算法通常可以按以下三类情况进行分析:
最坏情况
最坏情况是指算法对于一类问题样本表现出的最坏性能。通常,算法设计人员在描述最坏情况时,会指出导致算法无法高效执行的输入数据的特征,而并非找出特定的输入数据。
平均情况
平均情况是指算法在随机给定的数据上期望的执行情况。某些问题样本可能会由于一些特例而导致程序需要更长的时间才能完成,但是大多数情况都并非如此。平均情况描述了一般用户对算法性能的期望。
最好情况
最好情况是指算法对于一类问题样本表现出的最好性能。对于这类样本,算法只需要执行很少的计算。在实际情况中,最好情况很少出现。
通过了解算法在每种情况下的性能,读者就能判断它是否适用于特定场景。
2017_09_19_154018
图2-3:第四种排序算法在处理几乎有序的数据时性能最好

相关文章
|
5天前
|
SQL 存储 算法
【MySQL技术内幕】6.4-锁的算法
【MySQL技术内幕】6.4-锁的算法
21 1
|
5天前
|
存储 算法 关系型数据库
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
12 1
|
7天前
|
算法 C语言 Ruby
分形逃逸时间算法中的 Normalized Iteration Count(NIC)技术 让颜色更柔和
Normalized Iteration Count (NIC) 技术是一种提升逃逸时间算法中分形图像质量的方法,它产生更平滑的颜色过渡。数学公式表示为:`mu = n + 1 - log(log(|Z(n)|)) / log(p)`,其中 `Z(n)` 是迭代次数,`|Z(n)|` 是复数模长,`p` 通常取2。示例代码提供了 Ruby, Maxima 和 C 语言的实现。
|
9天前
|
存储 自然语言处理 算法
编辑距离算法全解析:优化文本处理的关键技术
编辑距离算法全解析:优化文本处理的关键技术
|
12天前
|
存储 算法
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
16 0
|
12天前
|
存储 运维 算法
社交软件红包技术解密(十三):微信团队首次揭秘微信红包算法,为何你抢到的是0.01元
本文中,我们将介绍几种主流的IM红包分配算法,相信聪明的你一定能从中窥见微信红包技术实现的一些奥秘。
13 0
|
1月前
|
算法 Unix Linux
【C/C++ 实用工具】性能分析工具一览
【C/C++ 实用工具】性能分析工具一览
57 0
|
1月前
|
Rust 数据可视化 安全
Rust性能分析工具概览:perf、flamegraph 与其他
Rust作为一种高性能、内存安全的编程语言,在构建大型系统和微服务时备受青睐。然而,优化Rust程序的性能需要有效的工具。本文将对Rust中常用的性能分析工具进行介绍,包括perf、flamegraph等,并探讨它们如何帮助开发者定位和解决性能瓶颈。
|
1月前
|
数据可视化 关系型数据库 编译器
【C/C++ 单线程性能分析工具 Gprof】 GNU的C/C++ 性能分析工具 Gprof 使用全面指南
【C/C++ 单线程性能分析工具 Gprof】 GNU的C/C++ 性能分析工具 Gprof 使用全面指南
262 2
|
1月前
|
Web App开发 JavaScript 前端开发
JavaScript中的性能优化:代码优化技巧与性能分析工具
【4月更文挑战第22天】本文探讨JavaScript性能优化,包括代码优化技巧和性能分析工具。建议避免全局查找、减少DOM操作、使用事件委托、优化循环和异步编程以提升代码效率。推荐使用Chrome DevTools、Lighthouse和jsPerf等工具进行性能检测和优化。持续学习和实践是提升JavaScript应用性能的关键。