文档章节

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

浮躁的码农
 浮躁的码农
发布于 2015/08/20 08:43
字数 1776
阅读 32
收藏 0
点赞 0
评论 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))。怎样修改呢? 预先计算好某一输入的答案,在算法的开始部分判断输入,如果符合,给出答案。

本文转载自:

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

浮躁的码农

粉丝 57
博文 609
码字总数 141390
作品 0
松江
程序员
java 通配符的应用— java 排序算法

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

天地一MADAO_ ⋅ 2014/03/02 ⋅ 0

算法时间复杂度分析

常用的算法的时间复杂度和空间复杂度 1、时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机...

Angel13 ⋅ 2011/04/07 ⋅ 0

[译] 排序算法入门 — Go 语言实现

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

Go语言学习园地博客 ⋅ 2017/07/09 ⋅ 0

算法导论——算法分析

关于算法分析中O Ω Θ 算法的分析都是渐进分析,而并非是准确的数学分析,所以一些常用的符号需要熟记 O是算法复杂度的上界函数,用来衡量算法的最坏情况的复杂度 Ω是算法复杂度的下界函数...

姜宇 ⋅ 2011/05/11 ⋅ 0

插入排序标准C语言实现

算法描述 一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下: 从第一个元素开始,该元素可以认为已经被排序 取出下一个元素,在已经排序的元素序列中从后向前扫描 如果该元素...

liusir ⋅ 2012/05/05 ⋅ 0

趣学算法系列-算法之美

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

wwlcsdn000 ⋅ 2017/11/21 ⋅ 0

六个排序算法

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

刀狂剑痴 ⋅ 2016/05/12 ⋅ 0

【源码共享】快速排序算法的几种实现方式

快速排序算法的基本特性 时间复杂度:O(nlgn) 最坏:O(n^2) 空间复杂度:O(nlgn) 不稳定。 快速排序是一种排序算法,对包含n个数的输入数组,平均时间为O(nlgn),最坏情况是O(n^2)...

Master_Li ⋅ 2016/10/08 ⋅ 0

java数据结构之排序--> 插入排序算法

直接插入排序(Straight Insertion Sort)是一种简单的;排序方法,基本思想是每趟将一条待排序的记录,按其关键字值的大小插入到前面已经排好序列的记录之中的适当位置直到全部记录插入完为...

狂奔啦蜗牛 ⋅ 2012/08/19 ⋅ 0

算法——时间复杂度和空间复杂度

一、时间复杂度 T(n) = O(f(n)) 随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称之为算法的渐进时间复杂度,即时间复杂度,其中f(n)是问题n的函数 随着问题规模n的增大,T...

翼动动空 ⋅ 2016/05/09 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

如何解决s权限位引发postfix及crontab异常

一、问题现象 业务反馈某台应用服务器,普通用户使用mutt程序发送邮件时,提示“postdrop warning: mail_queue_enter: create file maildrop/713410.6065: Permission denied”,而且普通用法...

问题终结者 ⋅ 20分钟前 ⋅ 0

Unable to load database on disk

由于磁盘空间满了以后,导致zookeeper异常退出,清理磁盘空间后,zk启动报错,信息如下: 2018-06-25 17:18:46,904 INFO org.apache.zookeeper.server.quorum.QuorumPeerConfig: Reading co...

刀锋 ⋅ 39分钟前 ⋅ 0

css3 box-sizing:border-box 实现div一行多列

<!DOCTYPE html><html><head><style> div.container{ background:green; padding:10px 10px;}div.box{box-sizing:border-box;-moz-box-sizing:border-box; /* Fir......

qimh ⋅ 45分钟前 ⋅ 0

Homebrew简介和基本使用

一、Homebrew是什么 Homebrew是一款Mac OS平台下的软件包管理工具,拥有安装、卸载、更新、查看、搜索等很多实用的功能。简单的一条指令,就可以实现包管理,而不用你关心各种依赖和文件路径...

说回答 ⋅ 52分钟前 ⋅ 0

文件压缩和打包zip、tar

第六章 文件压缩和打包 6.5 zip压缩工具 zip命令可以用来解压缩文件,或者对文件进行打包操作。zip是个使用广泛的压缩程序,文件经它压缩后会另外产生具有“.zip”扩展名的压缩文件。 注意:...

弓正 ⋅ 53分钟前 ⋅ 0

vuex

一、状态对象如何赋值给内部对象。三种方式: 1、使用computed赋值,一定要写this,不然找不到$store。 computed:{ count(){ return this.$store.state.count; }} 2、通...

大美琴 ⋅ 今天 ⋅ 0

javaScript 设计模式

1、构造函数模式 ` /** 构造一个动物的函数 */ function Animal(name, color){ this.name = name; this.color = color; this.getName = function(){ return this.name; } } // 实例一个对象 ......

fangPeng_ ⋅ 今天 ⋅ 0

日常嘚瑟:TeamCity构建中解压和打包tar

要弄一个新的构建,很简单,从两个构建的tar格式Artifact中分别取一部分,重新打一个tar。 所以,我去写个脚本用curl下载两个依赖的Artifact,然后解压移动重新打个tar? 开什么玩笑,我的技...

谷永权 ⋅ 今天 ⋅ 0

Istio官方文档中文版

阅读目录 Istio官方文档中文版 回到目录 Istio官方文档中文版 http://istio.doczh.cn/ https://istio.io/docs/concepts/what-is-istio/goals.html 为什么要使用Istio? 在从单体应用程序向分...

xiaomin0322 ⋅ 今天 ⋅ 0

CentOS 7 Omnibus 包安装 GitLab 并汉化记录

系统环境 操作系统:CentOS 7GitLab:gitlab-ce-10.8.4-ce.0.el7.x86_64.rpm 下载Omnibus安装包 使用国内镜像加速下载地址 # wget https://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/yum/el......

admin_qing ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部