在排序数组中搜索的严格的较低时间复杂度是多少 [英] what is the tight lower time complexity bound for searching in a sorted array

问题描述

例如，在排序中，紧下限是 N*log(N)，其中 N 是数组的大小

For example, in sorting the tight lower bound is N*log(N) where N is the size of the array

如何在已排序的数组中进行搜索?我认为是 log(N) 但我不是 100% 确定.

how about for searching in a sorted array? I think it's log(N) but I'm not 100% sure.

同样一切都基于比较，除了输入数组本身之外，不能使用任何其他外部存储器

also everything is based on comparisons, no any other external memory than the input array itself can be used

提前致谢

推荐答案

搜索简单排序数组的最佳解决方案是二分搜索，其时间复杂度为 O(log₂(N)).最坏的情况发生在搜索元素不在数组中时，并且恰好需要 ⌊log₂(N) + 1⌋ 次迭代.请参阅二分搜索性能.

The optimal solution for searching a simple sorted array is a Binary Search, which has time complexity O(log₂(N)). The worst case happens when the searched-for element is not in the array, and takes exactly ⌊log₂(N) + 1⌋ iterations. See Binary Search Performance.

我相信在提到复杂性的上限和下限时，您只能谈论紧密度".下界(大欧米茄)通常更难计算，而且通常不如上界(大 O)有用.紧边界(大 Theta)同时考虑了上限和下限.

I believe you can only talk about "tightness" when referring to the upper AND lower bounds of complexity. Lower bound (big Omega) is generally more difficult to compute, and often not as useful as upper bound (big O). Tight bound (big Theta) takes both upper and lower bounds into account.

技术上的下限是Ω(1)，因为您可以在第一次比较中找到搜索到的元素.见 二分查找是 theta log (n) 还是 big Olog(n) 进一步讨论二分查找的时间复杂度.

Technically the lower bound is Ω(1), because you can find the searched-for element on the first comparison. See Is binary search theta log (n) or big O log(n) for further discussion of the time complexity of binary search.

这篇关于在排序数组中搜索的严格的较低时间复杂度是多少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！