algorithm - 使用二进制搜索对未列出的数组进行排序？

Question

如果我有一个未排序的数组并且我需要在不切换它们的情况下找到某个元素，我通常会使用线性搜索。但是，如果我决定使用快速排序或合并排序对整个数组进行排序，然后使用二进制搜索找到我想要查找的元素，然后我将重新排列数组以使其在开始时的样子。它的时间复杂度和空间复杂度是多少？使用更大的数据集会比线性搜索更有效吗？

标签： algorithmsortingsearchtime-complexity

Answer 1

不，这无助于提高时间复杂度。瓶颈将是排序（没有关于数据的任何可用假设）具有O(nlogn)时间复杂度，这比通过未排序数组进行线性搜索时获得的线性时间复杂度更差。

即使您拥有适合基数排序的数据类型，并获得具有线性时间复杂度的排序数组，这仍然不会改善您已经通过简单搜索获得的时间复杂度。

如果没有任何额外的信息，你不能做得比线性时间复杂度更好。当您意识到数组中的任何插槽都可以容纳您要查找的元素时，您可以轻松掌握这一点。因此，在最坏的情况下，它将是您查看数组中所有其他n -1 个插槽之后查看的最后一个插槽。因此，您执行了n次操作，这表示线性时间复杂度。

正如您还询问空间复杂度：排序可以就地完成，因此如果您仍然决定对数据进行排序，则对空间复杂度没有影响。