大O算法最短时间
Big O algorithms minimum time
我知道对于一些问题，无论你用什么算法来解决它，解决问题总是需要一定的最短时间。我知道 BigO 会捕获最坏情况（所需的最大时间），但是如何找到作为 n 函数所需的最短时间？我们能否找到排序 n 个整数所需的最短时间，或者也许找到 n 个整数中的最小值？
您要找的是best case complexity。对算法来说是一种无用的分析，最坏情况分析是最重要的分析，平均情况分析有时在特殊情况下使用。
最佳情况的复杂性取决于算法。例如，在线性搜索中，最好的情况是搜索到的数字位于数组的开头。或者在二进制搜索中，它位于第一个分界点。在这些情况下，复杂度为 O(1)。
对于单个问题，最佳情况的复杂度可能因算法而异。例如，以免讨论一些基本的排序算法。
- 在冒泡排序中，最好的情况是数组已经排序。但即使在这种情况下，您也必须检查所有元素才能确定。所以这里最好的情况是 O(n)。插入排序也是如此
- 对于 quicksort/mergesort/heapsort 最好的情况复杂度是 O(n log n)
- 对于选择排序，它是 O(n^2)
所以从上面的案例中你可以了解到复杂度（是最好的，最差的还是平均的）取决于算法，而不是问题
我知道对于一些问题，无论你用什么算法来解决它，解决问题总是需要一定的最短时间。我知道 BigO 会捕获最坏情况（所需的最大时间），但是如何找到作为 n 函数所需的最短时间？我们能否找到排序 n 个整数所需的最短时间，或者也许找到 n 个整数中的最小值？
您要找的是best case complexity。对算法来说是一种无用的分析，最坏情况分析是最重要的分析，平均情况分析有时在特殊情况下使用。
最佳情况的复杂性取决于算法。例如，在线性搜索中，最好的情况是搜索到的数字位于数组的开头。或者在二进制搜索中，它位于第一个分界点。在这些情况下，复杂度为 O(1)。
对于单个问题，最佳情况的复杂度可能因算法而异。例如，以免讨论一些基本的排序算法。
- 在冒泡排序中，最好的情况是数组已经排序。但即使在这种情况下，您也必须检查所有元素才能确定。所以这里最好的情况是 O(n)。插入排序也是如此
- 对于 quicksort/mergesort/heapsort 最好的情况复杂度是 O(n log n)
- 对于选择排序，它是 O(n^2)
所以从上面的案例中你可以了解到复杂度（是最好的，最差的还是平均的）取决于算法，而不是问题