为什么√n是跳跃搜索中m的最优值?

Question

我目前正在学习搜索算法，我遇到了跳跃搜索，它的时间复杂度为O(√n)。为什么√n是跳跃搜索算法中m(跳跃大小)的最优值，它是如何影响时间复杂度的?

Answer 1

设m为跳跃大小，n为元素个数。

在最坏的情况下，你需要检查的最大元素数量是最大跳跃次数(n/m - 1)加上跳跃之间的元素数量(m)，你所花费的时间大约与你检查的元素总数成正比。

因此，选择m的目标是最小化:(n/m)+m-1。

m的导数是1 - (n/m²)，最小值出现在导数为0的地方:

1 - (n/m²) = 0

(n/m²) = 1

n = m²

m =√n

Answer 2

假设块大小为k，在最坏的情况下，查找块大约需要n/k次迭代，查找块中的元素需要k次迭代。

要最小化n/k + k，其中n是常数，我们可以使用微分(参见Matt的答案)或AM-GM不等式得到:

n/k + k>= 2sq (n)

我们可以清楚地看到2sqrt(n)是最小迭代次数，当k = sqrt(n)时可以实现。