范文中国网后台-模板-公共模板变量-头部模板-自定义右侧文字

首页 > 励志 / 正文

第15话:算法的最坏情况与平均情况

2018-01-13 06:58:23 励志 0 评论

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

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

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

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

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

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

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

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

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

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

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

我以前问过老师,为什么要分析最坏情况下的算法时间复杂性?结果老师的答案是程序就是要看最差的时间,而且最差时间比较容易计算出来。

分页:12 
 1/2    1 2 下一页 尾页

Tags:情况  情况指什么  情况怎样的意思 

搜索
网站分类
标签列表
后台-系统设置-扩展变量-手机广告-栏目/内容页底部