algorithm - 大O算法最短时间

Question

我知道对于一些问题，无论你用什么算法来解决它，解决问题总是需要一定的最短时间。我知道 BigO 会捕获最坏情况(所需的最大时间)，但是如何找到作为 n 函数所需的最短时间？我们能否找到排序 n 个整数所需的最短时间，或者也许找到 n 个整数中的最小值？

Answer 1

您正在寻找的是best case complexity。对算法来说是一种无用的分析，最坏情况分析是最重要的分析，平均情况分析有时在特殊场景下使用。

最佳情况的复杂性取决于算法。例如，在线性搜索中，最好的情况是搜索到的数字位于数组的开头。或者在二进制搜索中，它位于第一个分界点。在这些情况下，复杂度为 O(1)。

对于单个问题，最佳情况复杂度可能因算法而异。例如，以免讨论一些基本的排序算法。

1. 在冒泡排序中，最好的情况是数组已经排序。但即使在这种情况下，您也必须检查所有元素才能确定。所以这里最好的情况是 O(n)。插入排序也是如此
2. 对于快速排序/合并排序/堆排序，最好的情况复杂度是 O(n log n)
3. 对于选择排序是 O(n^2)

所以从上面的案例你可以理解复杂度(是最好的，最坏的还是平均的)取决于算法，而不是问题本身