二进制搜索未排序数组的时间复杂度

我被两个时间的复杂性困住了。使用排序数组进行二分搜索是O（logN）。所以要搜索一个未排序的数组，我们必须首先对它进行排序，以便变成O（NlogN）。那么我们可以执行二进制搜索，其复杂度为O（N），但我已经读过它可能是O（NlogN）。哪个是对的？二进制搜索未排序数组的时间复杂度

来源

2013-04-09 user1521306

这些是两个独立的操作。无论如何，二分查找总是** O（log n）**。 – squiguy 2013-04-09 21:35:21

确实，二进制搜索不适用于未排序的数组;但是，您首先必须对数组进行排序以执行二分搜索。至少这是我最近学到的。 – user2373448 2017-11-21 21:16:36

二进制搜索用于“排序”列表。复杂度是O（logn）。

二进制搜索不适用于“未排序”列表。对于这些列表，只需从第一个元素开始直接搜索;这给出了O（n）的复杂度。如果要使用MergeSort或任何其他O（nlogn）算法对数组进行排序，则复杂度将为O（nlogn）。

O（LOGN）< O（n）的< O（nlogn）

来源

2013-04-09 21:31:55 LuiNova

即使数组有点小但未排序，BinarySearch仍然可以工作。好注意。 – ofarooq 2016-12-27 18:21:34

回答你的问题是你的问题本身。您首先对列表进行排序。如果使用快速排序或合并排序对列表进行排序，则复杂度将变为o（n log n）。第一部分结束。执行二进制搜索的第二部分是在“分类列表”上完成的。二进制搜索的复杂度是o（log n）。因此，最终程序的复杂性仍然是o（n日志n）n（n =）。但是，如果您想计算数组的中位数，则不必对列表进行排序。线性或顺序搜索的简单应用可以帮助您。

来源

2013-12-02 18:19:03 yuvrajm

线性搜索的时间复杂度为O(n)，二分查找的时间复杂度为O(log n)（对数基数为2）。如果我们有一个未排序的数组，并且想要使用二进制搜索，我们必须首先对数组进行排序。在这里，我们必须花费时间O(n logn)对数组进行排序，然后花时间搜索元素。

来源

2016-11-19 06:37:31

二进制搜索未排序数组的时间复杂度

回答

相关问题