algorithm - 元素搜索成本

Question

我有一个由 n 个元素组成的数组。这些元素是数字。我现在要做的是在我的数组中找到很多。我将不得不进行sqrt(n)搜索。

从效率的角度来看，什么是对我更好的选择？

1. 线性搜索
2. 数组排序（让我们说线性时间，例如，当我们使用 RadixSort 时）然后使用二分搜索搜索元素 -O(logn)

我有一些直觉，但我不知道如何检查和证明。线性搜索成本是（在最坏的情况下）:) O(n) * O(sqrt(n)。排序后的二进制搜索将是O(n) + O(logn) * O(sqrt(n)).

Answer 1

正如你所说，你有两个选择：

1. 线性搜索sqrt(n)时间。成本是O(n * sqrt(n))。
2. 对数组进行排序O(n)，然后是二进制搜索sqrt(n)时间。
   成本是O(n + log(n) * sqrt(n))。对于所有积极的人来说都n更大。 证明。 多亏了这一点，我们可以写. 排序部分占主导地位，这是瓶颈。log(n) * sqrt(n)n
O(n + log(n) * sqrt(n)) = O(n)
   

因此，对于 big ，第二种方法n应该更快 - 近似线性。

Answer 2

您有两种方法可以解决您的问题：

1. 排序然后搜索
2. 只是搜索

制作一张复杂性表格，您将获得解决方案。也许你可以使用像http://rechneronline.de/function-graphs/这样的工具来比较两个复杂性。

您有不同的情况：

1. 线性搜索 sqrt(n) 次 = O(n * sqrt(n))。
2. 线性排序然后二分查找 sqrt(n) 次 = O(n) + O(log(n) * sqrt(n)= O(n)

第二个似乎是最有希望的。