算法的最优、最劣和平均运行时间是什么?
算法的最优、最劣和平均运行时间是什么?
简单来说,对于输入大小为n的问题:
最佳情况 = 完成所需的最快时间,使用最优输入。
例如,排序算法的最佳情况是数据已经排序好。
最坏情况 = 完成所需的最慢时间,使用最劣输入。
例如,某些排序算法的最坏情况可能是按相反顺序排序的数据(但这取决于具体的算法)。
平均情况 = 算术平均数。 运行该算法多次,使用许多不同的大小为n的输入,这些输入来自生成这些输入的某个分布(在最简单的情况下,所有可能的输入都是等可能的),计算总运行时间(通过添加各个时间),并除以试验次数。 您还可能需要根据输入集的大小对结果进行规范化。
复杂度和运行时间通常用“大O符号”表示,用于描述算法基于其输入大小需要完成的近似时间量。 Rob Bell编写了一篇非常清晰的文章,其中包含非常明确的示例。
最常用的大O描述是:
您可以从下面的表格中看到,对于小的输入大小,差异很小,但是即使输入大小略微增加,差异也会变得非常大。
输入规模 完成时间 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最坏情况分析(通常使用) 在最坏情况分析中,我们计算算法运行时间的上限。我们必须知道导致执行操作次数最多的情况。对于线性搜索,当要搜索的元素(如上述代码中的x)不在数组中时,最坏情况发生。当x不存在时,search()函数将逐个与arr[]中所有元素进行比较。因此,线性搜索的最坏时间复杂度为Θ(n)。
平均情况分析(有时使用) 在平均情况分析中,我们考虑所有可能的输入,并计算所有输入的计算时间。将所有计算出的值相加,然后除以输入的总数。我们必须了解(或预测)情况的分布。对于线性搜索问题,让我们假设所有情况都是均匀分布的(包括x不在数组中的情况)。因此,我们将所有情况相加,然后除以(n+1)。以下是平均情况时间复杂度的值。
最佳情况分析(虚假) 在最佳情况分析中,我们计算算法运行时间的下限。我们必须知道导致执行操作次数最少的情况。在线性搜索问题中,最佳情况发生在x在第一个位置的情况下。最佳情况下的操作次数是固定的(不取决于n)。因此,最佳情况下的时间复杂度为Θ(1)。
最坏情况通常用渐进符号即Big(O)来表示
最好情况通常用渐进符号即Big(OMEGA)来表示
最好的情况是,如果某些东西已经排序好了,那么就不需要做任何工作。 最坏的情况(取决于您的算法),但请考虑什么会导致您的算法花费最长的时间。
算法的运行时间取决于输入的大小和“复杂性”。
例如,对于某个大小为n的输入,插入排序的最佳情况运行时间与n成比例,即对于某个常数c,需要c*n的时间单位,这取决于您的计算模型中比较、算术等的成本(时间)。该算法(插入排序)的最坏情况运行时间与n*n成比例。要对平均时间进行说明,我们需要对输入数据的分布做出一些假设:例如,如果输入是随机数据(因此可能未排序),则平均运行时间再次与n*n成比例。
如果您了解有关输入数据的更多信息,例如它按降序排序(而我们正在按升序排序),则平均运行时间仍然与n*n成比例,但常数因子更高(因为查找最小值的平均时间(将插入到已排序子列表的末尾)需要更长时间)。
另一个更复杂的例子是快速排序:对于随机数据,其平均和最佳运行时间与 n * log n 成正比。最坏情况下的时间仍然是 n * n(通常是针对已经排序好的输入,但这取决于在分割步骤中查找枢轴元素的算法)。