我有两次复杂的困难 . 使用有序数组进行二进制搜索是O（logN） . 因此，要搜索未排序的数组，我们必须先对其进行排序，以便变为O（NlogN） . 那么我们就可以执行二进制搜索，它给出的复杂度为O（N），但我已经读过它可能是O（NlogN） . 哪个是对的？
二进制搜索用于“已排序”列表 . 复杂性是O（logn） .
二进制搜索不适用于“未排序”列表 . 对于这些列表，只需从第一个元素开始直接搜索;这给出了O（n）的复杂性 . 如果您使用MergeSort或任何其他O（nlogn）算法对数组进行排序，那么复杂度将为O（nlogn） .
O（logn）<O（n）<O（nlogn）
你问题的答案就在你的问题中 .
您首先对列表进行排序 . 如果使用快速排序或合并排序对列表进行排序，则复杂性变为 o(n*log n) . 第一部分结束了 .
o(n*log n)
执行二进制搜索的第二部分是在'Sorted list'上完成的 . 二进制搜索的复杂性是 o(log n) . 因此，该计划的复杂性最终仍然是 o(n*log n) .
o(log n)
但是，如果要计算数组的中位数，则不必对列表进行排序 . 线性或顺序搜索的简单应用可以帮助您 .
线性搜索的时间复杂度为 O(n) ，二进制搜索的时间复杂度为 O(log n) （log base-2） . 如果我们有一个未排序的数组并且想要使用二进制搜索，我们必须先对数组进行排序 . 在这里，我们必须花费一些时间 O(n logn) 对数组进行排序，然后花时间搜索元素 .
O(n)
O(log n)
O(n logn)
3 回答
二进制搜索用于“已排序”列表 . 复杂性是O（logn） .
二进制搜索不适用于“未排序”列表 . 对于这些列表，只需从第一个元素开始直接搜索;这给出了O（n）的复杂性 . 如果您使用MergeSort或任何其他O（nlogn）算法对数组进行排序，那么复杂度将为O（nlogn） .
O（logn）<O（n）<O（nlogn）
你问题的答案就在你的问题中 .
您首先对列表进行排序 . 如果使用快速排序或合并排序对列表进行排序，则复杂性变为
o(n*log n). 第一部分结束了 .执行二进制搜索的第二部分是在'Sorted list'上完成的 . 二进制搜索的复杂性是
o(log n). 因此，该计划的复杂性最终仍然是o(n*log n).但是，如果要计算数组的中位数，则不必对列表进行排序 . 线性或顺序搜索的简单应用可以帮助您 .
线性搜索的时间复杂度为
O(n)，二进制搜索的时间复杂度为O(log n)（log base-2） . 如果我们有一个未排序的数组并且想要使用二进制搜索，我们必须先对数组进行排序 . 在这里，我们必须花费一些时间O(n logn)对数组进行排序，然后花时间搜索元素 .