问二进制搜索复杂度

EN

对于整个程序，答案是：O(logn) + O(n) = O(n)：

为什么会这样呢？因为将n个数字输入数组和二进制搜索是相互独立的。

现在，我们需要全面了解time complexity：

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

最佳情况=最快的完成时间，并选择最佳输入。例如，排序算法的最佳情况是已经排序的数据。

最坏情况=最慢的完成时间，并选择了悲观的输入。例如，排序算法的最坏情况可能是按反向顺序排序的数据(但这取决于特定的算法)。

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

示例(二进制搜索)：

假设我们有以下二进制搜索函数：

binarySearch(arr, x, low, high)
        repeat till low = high
               mid = (low + high)/2
                   if (x == arr[mid])
                   return mid
   
                   else if (x > arr[mid]) // x is on the right side
                       low = mid + 1
   
                   else                  // x is on the left side
                       high = mid - 1

现在，让我们分析一下它的time complexity。

二值搜索的最佳情况时间复杂度

二进制搜索的最佳情况是：

要搜索的元素位于列表的中间，在本例中，元素是在第一步中找到的，这需要进行1次比较。

因此，二进制搜索的最佳情况时间复杂度是O(1)。

二值搜索的平均案例时间复杂度

设输入N个不同的数字: a1，a2，.，a(N-1)，aN

我们需要找到P元素。

有两种情况：

案例1:元素P可以位于从0到N1的N个不同的索引中.

案例2:当元素P不在列表中时，就会出现。有N例1和1例2，因此，总有N+1不同的情况需要考虑。

如果元素P在索引K中，则二进制搜索将进行K+1比较。

这是因为：

当二进制搜索从中间开始时，在索引N/2处的元素可以在1比较中找到。

同样，在第二次比较中，根据第一次比较的结果，对指数N/4和3N/4处的元素进行了比较。

在第三次比较中，根据第二次比较的结果，对指数N/8、3N/8、5N/8、7N/8的元素进行了比较。

基于此，我们知道：

需要1项比较的要素:1项需要2项比较的要素；2项需要3项比较的要素:4

因此，需要i比较的元素: 2^(I-1)

最大比较数=N的次数除以2，结果为1=比较，达到第1元素= logN比较

我可以从0到logN不等

比较总数=1*(需要1比较的元素)+2*(需要2比较的元素)+.+ logN *(需要logN比较的元素)

比较总数=1* (1) +2* (2) +3* (4) +.+ logN * (2^(logN-1))

比较总数=1+4+ 12 + 32 +.= 2^logN * (logN - 1) +1

比较总数=N* (logN - 1) +1

案件总数= N+1

因此，平均比较数=(N* (logN - 1) +1)/ (N+1)

平均比较数=N* logN / (N+1) - N/(N+1) + 1/(N+1)

优势项是N* logN / (N+1)，近似为logN。因此，二进制搜索的平均时间复杂度为O(logN).Let有N个不同的数字: a1，a2，.，a(N-1)，aN

我们需要找到P元素。

有两种情况：

案例1:元素P可以位于从0到N1的N个不同的索引中.

案例2:当元素P不在列表中时，就会出现。有N例1和1例2，因此，总有N+1不同的情况需要考虑。

如果元素P在索引K中，则二进制搜索将进行K+1比较。

这是因为：

当二进制搜索从中间开始时，在索引N/2处的元素可以在1比较中找到。

同样，在第二次比较中，根据第一次比较的结果，对指数N/4和3N/4处的元素进行了比较。

在第三次比较中，根据第二次比较的结果，对N/8、3N/8、5N/8和7N/8的元素进行了比较。

基于此，我们知道：

需要1比较的元素:1需要2比较的元素:2需要3比较的元素:4因此，需要I比较的元素: 2^(I-1)

最大比较数=N的次数除以2，结果为1=比较，达到第1元素= logN比较

我可以从0到logN不等

比较总数=1*(需要1比较的元素)+2*(需要2比较的元素)+.+ logN *(需要logN比较的元素)

比较总数=1* (1) +2* (2) +3* (4) +.+ logN * (2^(logN-1))

比较总数=1+4+ 12 + 32 +.= 2^logN * (logN - 1) +1

比较总数=N* (logN - 1) +1

案件总数= N+1

因此，平均比较数=(N* (logN - 1) +1)/ (N+1)

平均比较数=N* logN / (N+1) - N/(N+1) + 1/(N+1)

优势项是N* logN / (N+1)，近似为logN。因此，二进制搜索的平均时间复杂度为O(logN)。

最坏情况下二值搜索的时间复杂度

二进制搜索的最坏情况是：

在本例中，要搜索的元素位于第一个索引或最后一个索引中，所需的比较总数为logN比较。

因此，二进制搜索的最坏的时间复杂度是O(logN)。