logo标签列表

算法的最佳、最差和平均运行时间是什么？

algorithmtime-complexitycomputer-science
13

算法的最优、最劣和平均运行时间是什么？

我删除了“操作系统”标签，因为它与问题无关。 - ffriend
是的...但我找不到一个完美的答案。 - Grant
我投票关闭此问题，因为它在这里是离题的。这不是一个真正的编程问题，而是一个理论计算机科学问题，所以应该在计算机科学堆栈交换上问。 - nbro
6个回答
38

简单来说，对于输入大小为n的问题：

  • 最佳情况 = 完成所需的最快时间，使用最优输入。
    例如，排序算法的最佳情况是数据已经排序好。

  • 最坏情况 = 完成所需的最慢时间，使用最劣输入。
    例如，某些排序算法的最坏情况可能是按相反顺序排序的数据（但这取决于具体的算法）。

  • 平均情况 = 算术平均数。 运行该算法多次，使用许多不同的大小为n的输入，这些输入来自生成这些输入的某个分布（在最简单的情况下，所有可能的输入都是等可能的），计算总运行时间（通过添加各个时间），并除以试验次数。 您还可能需要根据输入集的大小对结果进行规范化。

复杂度和运行时间通常用“大O符号”表示，用于描述算法基于其输入大小需要完成的近似时间量。 Rob Bell编写了一篇非常清晰的文章，其中包含非常明确的示例。

最常用的大O描述是：

  • O(1)始终在大约相同的时间内终止，无论输入大小如何。
  • O(logN)每当输入大小加倍时，需要固定的额外时间。
  • O(N)如果输入大小加倍，则需要两倍的时间来完成。
  • O(N2)如果输入大小翻倍，则需要四倍的时间来完成。
  • O(2N)随着输入大小的增加呈指数级增长。

您可以从下面的表格中看到，对于小的输入大小，差异很小，但是即使输入大小略微增加，差异也会变得非常大。

输入规模       完成时间
O(1)   O(logN)  O(N)  O(N2)  O(2N)
1           1        1      1        1         1
2           1        2      2        4         4
4           1        3      4       16        16
8           1        4      8       64       256
16          1        5     16      254    65536
并且是错误的。首先，所有三个都与固定的输入大小n有关。否则，“最坏”或“最好”可能无法定义明确。其次，平均情况是指对所有输入（这个给定的大小）取平均值，并加权一些概率分布（通常是均匀分布）。 - Raphael
需要注意的是，最好情况或最坏情况与输入大小无关，而与输入的性质有关。例如，列表是否已排序。 - Oloff Biermann
4

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

平均情况分析（有时使用） 在平均情况分析中，我们考虑所有可能的输入，并计算所有输入的计算时间。将所有计算出的值相加，然后除以输入的总数。我们必须了解（或预测）情况的分布。对于线性搜索问题，让我们假设所有情况都是均匀分布的（包括x不在数组中的情况）。因此，我们将所有情况相加，然后除以(n+1)。以下是平均情况时间复杂度的值。

最佳情况分析（虚假） 在最佳情况分析中，我们计算算法运行时间的下限。我们必须知道导致执行操作次数最少的情况。在线性搜索问题中，最佳情况发生在x在第一个位置的情况下。最佳情况下的操作次数是固定的（不取决于n）。因此，最佳情况下的时间复杂度为Θ(1)。

算法分析 - 第2部分：渐进分析在计算机科学中，我们经常需要评估算法的效率。一个算法的效率取决于它所需的时间和空间。但是，这些因素受到许多因素的影响，例如硬件、操作系统等。因此，我们需要一种方法来评估算法的效率，而不受这些因素的影响。渐进分析是一种用于评估算法效率的技术。它考虑了算法的输入大小，并且随着输入大小的增加，算法所需的时间和空间如何变化。渐进分析使用大O符号表示算法的时间复杂度和空间复杂度。在本文中，我们将介绍渐进分析的概念，并通过几个示例说明如何使用它来评估算法的效率。 - Yasser Shaikh
2
将算法视为程序。该程序接受一些数据，对其进行处理一段时间，然后输出答案。当然，我们关心程序在提供答案之前处理数据的时间有多长。
但是有个问题：对于许多算法而言，运行时间取决于数据本身。例如，许多排序算法对已排序数据速度更快，对反向排序的数据速度最慢。
因此，让我们考虑数据来自哪里。也许你的好朋友可以挑选数据。你的朋友选择能使程序快速运行的数据，我们称这个运行时间为最佳情况，因为算法永远不会比这个更好。也许你的死敌（在教科书中，这被称为对手）可以挑选数据。你的死敌选择能让程序运行缓慢的数据，我们称这个运行时间为最坏情况，因为算法永远不会比这个更差。也许一个巨大的轮盘赌会挑选你的数据。那么，你可以在一堆轮盘赌数据上运行你的算法，并将所有运行时间平均以得到平均情况时间。
谢谢你的答案和帮助我 :) - Grant
1

最坏情况通常用渐进符号即Big(O)来表示

最好情况通常用渐进符号即Big(OMEGA)来表示

1

最好的情况是，如果某些东西已经排序好了，那么就不需要做任何工作。 最坏的情况（取决于您的算法），但请考虑什么会导致您的算法花费最长的时间。

1

算法的运行时间取决于输入的大小和“复杂性”。

例如，对于某个大小为n的输入，插入排序的最佳情况运行时间与n成比例，即对于某个常数c，需要c*n的时间单位，这取决于您的计算模型中比较、算术等的成本（时间）。该算法（插入排序）的最坏情况运行时间与n*n成比例。要对平均时间进行说明，我们需要对输入数据的分布做出一些假设：例如，如果输入是随机数据（因此可能未排序），则平均运行时间再次与n*n成比例。

如果您了解有关输入数据的更多信息，例如它按降序排序（而我们正在按升序排序），则平均运行时间仍然与n*n成比例，但常数因子更高（因为查找最小值的平均时间（将插入到已排序子列表的末尾）需要更长时间）。

另一个更复杂的例子是快速排序：对于随机数据，其平均和最佳运行时间与 n * log n 成正比。最坏情况下的时间仍然是 n * n（通常是针对已经排序好的输入，但这取决于在分割步骤中查找枢轴元素的算法）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接