文档章节

算法的最坏情况与平均情况

浮躁的码农
 浮躁的码农
发布于 2015/08/20 08:43
字数 1776
阅读 33
收藏 0

如果一个程序运行多次,则有时候它会快点儿,有时候它会慢点儿。算法也一样,在输入1的情况下和输入2的情况下,其执行效率不一定一样。即算法会随着输入数据的不同而有秩序效率的不同,有时候会快点儿,有时候会慢点儿。例如,对一个已经排好序的序列进行排序就要相对容易一些。另外,输入规模的大小也影响算法的运行时间。例如,一个短的序列就比一个很长的序列容易排序。

一般来说,我们希望获得一个算法的时间效率下限,因为所有人都喜欢某种保证:即算法无论如何不会低于我们保证的效率。这种分析就是所谓的最坏情况分析。最坏情况分析指的是在给定输入尺寸的情况下,一个算法运行的效率的下限。

  • 比如早晨上班出门后突然想起来,手机忘记带了,这年头,钥匙、钱包、手机三大件,出门哪样也不能少呀。于是回家找。打开门一看,手机就在门口玄关的台子上,原来是出门穿鞋时忘记拿了。这当然是比较好,基本没花什么时间寻找。可如果不是放在那里,你就得进去到处找,找完客厅找卧室、找完卧室找厨房、找完厨房找卫生间,就是找不到,时间一分一秒的过去,你突然想起来,可以用家里座机打一下手机,听着手机铃声来找呀,真是笨。终于找到了,在床上枕头下面。你再去上班,迟到。见鬼,这一年的全勤奖,就因为找手机给黄了。

找东西有运气好的时候,也有怎么也找不到的情况。但在现实中,通常我们碰到的绝大多数既不是最好的也不是最坏的,所以算下来是平均情况居多。

算法(Algorithms)的复杂度(Complexity)是指运行一个算法所需消耗的资源(时间或者空间)。同一个算法处理不同的输入数据所消耗的资源也可能不同,所以分析一个算法的复杂度时,主要有三种情况可以考虑,最差情况(Worst Case)下的,平均情况(Average Case)的, 最好情况(Best Case)下的。

算法的分析也是类似,我们查找一个有n个随机数字数组中的某个数字,最好的情况是第一个数字就是,那么算法的时间复杂度为O(1),但也有可能这个数字就在最后一个位置上待着,那么算法的时间复杂度就是O(n),这是最坏的一种情况了。

最坏情况运行时间是一种保证,那就是运行时间将不会再坏了。在应用中,这是一种最重要的需求,通常,除非特别指定,我们提到的运行时间都是最坏情况的运行时间。

而平均运行时间也就是从概率的角度看,这个数字在每一个位置的可能性是相同的,所以平均的查找时间为n/2次后发现这个目标元素。平均情况更能反映大多数情况下算法的表现。平均情况分析就是对所有输入尺寸为n的输入,让算法运转一遍,然后取它们的平均值。当然,实际中不可能将所有可能的输入都运行一遍,因此平均情况通常指的是一种数学期望值,而计算数学期望值则需要对输入的分布情况进行假设。

平均运行时间是所有情况中最有意义的,因为它是期望的运行时间。也就是说,我们运行一段程序代码时,是希望看到平均运行时间的。可现实中,平均运行时间很难通过分析得到,一般都是通过运行一定数量的实验数据后估算出来的。

有时候我们还需要知道最好情况是什么,这有两层意义:一是我们想知道如果运气好,能好到什么程度;二是如果我们能够证明好运气与我们同在,当然需要知道运气好的时候算法表现如何。这种最好分析就是在给定输入规模的时候,看看哪种输入能使算法的运行最有效率。当然,有人认为这种最好情况分析有点假:我们可以操控输入来使一个本来很慢的算法表现得很快,从而达到蒙蔽人的效果。

对算法的分析,一种方法是计算所有情况的平均值,这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度,这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下,都是指最坏时间复杂度。

  • 我以前问过老师,为什么要分析最坏情况下的算法时间复杂性?结果老师的答案是程序就是要看最差的时间,而且最差时间比较容易计算出来。
  • 嗯,这是个原因。大概还有下面的一些原因:
  1. 最差情况下的复杂度是所有可能的输入数据所消耗的最大资源,如果最差情况下的复杂度符合我们的要求,我们就可以保证所有的情况下都不会有问题。
  2. 某些算法经常遇到最差情况。比如一个查找算法,经常需要查找一个不存在的值。
  3. 也许你觉得平均情况下的复杂度更吸引你,可是平均情况也有几点问题。第一,难计算,多数算法的最差情况下的复杂度要比平均情况下的容易计算的多,第二,有很多算法的平均情况和最差情况的复杂度是一样的. 第三,什么才是真正的平均情况?如果你假设所有可能的输入数据出现的概率是一样的话,也是不合理的。其实多数情况是不一样的。而且输入数据的分布函数很可能是你没法知道。
  4. 考虑最好情况的复杂度更是没有意义。几乎所有的算法你都可以稍微修改一下,以获得很好的最好情况下的复杂度(要看输入数据的结构,可以是O(1))。怎样修改呢? 预先计算好某一输入的答案,在算法的开始部分判断输入,如果符合,给出答案。

本文转载自:

共有 人打赏支持
浮躁的码农

浮躁的码农

粉丝 65
博文 746
码字总数 145372
作品 0
松江
程序员
私信 提问
java 通配符的应用— java 排序算法

这几天无聊,又重新学起java的排序算法,为DualPivotQuickSort做准备。为了更好地适应各种情况,我们选择使用通用类型T和通配符的上下界来实现,同时这次谈的是对数组对象的排序。如果你对j...

天地一MADAO_
2014/03/02
0
0
[译] 排序算法入门 — Go 语言实现

[译] 排序算法入门 — Go 语言实现 Go语言学习园地博客2017-07-0915 阅读 go算法排序 排序算法是一种采用列表或数组并以特定顺序对其元素进行重新排序的算法。有几十种不同的排序算法,如果你...

Go语言学习园地博客
2017/07/09
0
0
六个排序算法

排序算法 这是一共列表六个算法,冒泡,选择,插入,归并,希尔,快速,此外还有快速排序中枢选择不同的算法。 冒泡排序 最简单的排序方法了,从第一个元素循环到最后一个元素。对比相邻元素...

刀狂剑痴
2016/05/12
39
0
趣学算法系列-算法之美

趣学算法系列-算法之美 声明:本系列为趣学算法一书学习总结内容,在此推荐大家看这本算法书籍作为算法入门, 原作者博客链接,本书暂无免费电子版资源,请大家支持正版 书籍简介 本书内容按照...

wwlcsdn000
2017/11/21
0
0
排序总结(不断更新)

排序法 最好时间分析 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n)(改进的冒泡排序) O(n2) O(n2) 稳定 O(1) 快速排序 O(nlog2n) O(n2) O(nlog2n) 不稳定 O(log2n)~O(n) ...

Hosee
2015/10/23
786
0

没有更多内容

加载失败,请刷新页面

加载更多

ConcurrentHashMap 高并发性的实现机制

ConcurrentHashMap 的结构分析 为了更好的理解 ConcurrentHashMap 高并发的具体实现,让我们先探索它的结构模型。 ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEnt...

TonyStarkSir
今天
3
0
大数据教程(7.4)HDFS的java客户端API(流处理方式)

博主上一篇博客分享了namenode和datanode的工作原理,本章节将继前面的HDFS的java客户端简单API后深度讲述HDFS流处理API。 场景:博主前面的文章介绍过HDFS上存的大文件会成不同的块存储在不...

em_aaron
昨天
2
0
聊聊storm的window trigger

序 本文主要研究一下storm的window trigger WindowTridentProcessor.prepare storm-core-1.2.2-sources.jar!/org/apache/storm/trident/windowing/WindowTridentProcessor.java public v......

go4it
昨天
6
0
CentOS 生产环境配置

初始配置 对于一般配置来说,不需要安装 epel-release 仓库,本文主要在于希望跟随 RHEL 的配置流程,紧跟红帽公司对于服务器的配置说明。 # yum update 安装 centos-release-scl # yum ins...

clin003
昨天
9
0
GPON网络故障处理手册

导读 为了方便广大网络工作者工作需要,特搜集以下GPON网络处理流程供大家学习参考。开始—初步定为故障—检查光纤状况—检查ONU状态--检查设备运行状态—检查设备数据配置—检查上层设备状态...

问题终结者
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部