欢迎,计算机科学与信息计算爱好者!

算法分析(最差,最佳以及平均分析)

算法 scott 来源:geeksforgeeks 9个月前 (12-31) 506次浏览 0个评论 扫描二维码
This entry is part 2 of 2 in the series 算法系列

在上一篇文章中,我们讨论了渐近分析如何克服天真的分析算法的问题。在本文中,我们将以线性搜索为例,并使用渐近分析对其进行分析。

我们可以用三种情况来分析算法:
1)最坏情况
2)平均情况
3)最佳情况

让我们考虑以下线性搜索的实现。

最坏情况分析(最常使用)
在最坏情况分析中,我们计算算法运行时间的上限。我们必须知道导致最大数量的操作执行的情况。对于线性搜索,当数组中不存在要搜索的元素(上述代码中的x)时,最坏的情况发生。当x不存在时,search()函数将其与arr []的所有元素一一比较。因此,线性搜索的最坏情况下时间复杂度将为Θ(n)。

平均案例分析(有时可用)
在平均案例分析中,我们获取所有可能的输入并计算所有输入的计算时间。将所有计算值求和,然后将总和除以输入总数。我们必须知道(或预测)案件的分布。对于线性搜索问题,让我们假设所有情况都是均匀分布的(包括x不在数组中的情况)。因此,我们将所有情况相加,然后将总和除以(n + 1)。以下是平均案例时间复杂度的值。

平均案例复杂度 \[\begin{array}{l}=\frac{\sum_{i=1}^{n+1} \theta(i)}{(n+1)}\\{=\frac{\theta((n+1) *(n+2) / 2)}{(n+1)}} \\{=\theta(n)}\end{array}\]

最佳案例分析(通常不可用)
在最佳案例分析中,我们计算算法运行时间的下限。我们必须知道导致最少数量的操作执行的情况。在线性搜索问题中,最好的情况是x在第一个位置出现。在最佳情况下,操作数是恒定的(不取决于n)。因此,最佳情况下的时间复杂度将为Θ(1)
。在大多数情况下,我们会进行最坏情况分析以分析算法。在最坏的分析中,我们保证了算法运行时间的上限,这是一个很好的信息。
在大多数实际案例中,平均案例分析并不容易,而且很少进行。在平均案例分析中,我们必须知道(或预测)所有可能输入的数学分布。
最佳案例分析是伪造的。确保算法的下限不会提供任何信息,因为在最坏的情况下,算法可能需要数年才能运行。

对于某些算法,所有情况在渐近上都是相同的,即,没有最坏和最好的情况。例如,合并排序。在所有情况下,合并排序都会执行Θ(nLogn)操作。其他大多数排序算法都有最坏的情况和最好的情况。例如,在“快速排序”的典型实现中(将枢轴选择为边角元素),当输入数组已被排序时,最坏的情况发生;当枢轴元素始终将数组分为两半时,最坏的情况发生。对于插入排序,最坏的情况发生在对数组进行反向排序时,最好的情况发生在以与输出相同的顺序对数组进行排序时。

Series Navigation<< 算法分析(渐近分析)

CSIT FUN , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:算法分析(最差,最佳以及平均分析)
喜欢 (4)
[985016145@qq.com]
分享 (0)
scott
关于作者:
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址