一个排序的数组二进制搜索的时间复杂度 [英] Time complexity of binary search for an unsorted array

问题描述

我被困了两个时间复杂度。做排序数组的二进制搜索是O（logn）时间。因此，要搜索的排序的数组，我们有这样变成O（NlogN）先排序。于是我们可以执行二进制搜索这给复杂度为O（N），但我已阅读，它可能是O（NlogN）。哪个是正确的？

I am stuck up with two time complexities. To do a binary search with sorted array is O(logN). So to search an unsorted array we have to sort it first so that becomes O(NlogN). So then we can perform binary search which gives the complexity as O(N) but I have read that it could be O(NlogN). Which is correct?

推荐答案

二进制搜索是排序名单。复杂度为O（LOGN）。

Binary Search is for "Sorted" lists. The complexity is O(logn).

二进制搜索不适用于非排序名单的工作。对于这些名单只是做从第一个元素开始直线搜索;这给出了一个O（n）的复杂性。如果你与归并或任何其他O（nlogn）算法排序的数组那么复杂性将是O（nlogn）。

Binary Search does not work for "un-Sorted" lists. For these lists just do a straight search starting from the first element; this gives a complexity of O(n). If you were to sort the array with MergeSort or any other O(nlogn) algorithm then the complexity would be O(nlogn).

O（LOGN）LT; O（N）LT; O（nlogn）

O(logn) < O(n) < O(nlogn)

这篇关于一个排序的数组二进制搜索的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！