在跳转搜索中如何找到跳块大小的最佳值？

Question

当m = √n时，函数((n/m) + m-1)的值将最小。因此，最佳步长为m = √n。 这里，n是数组的大小，m是被跳跃的块大小。

我明白n/m是我们在最坏的情况下做出的跳跃，m-1是我们找到区间(arr[km] < x < arr[(k+1)m])的线性搜索所花费的时间。

但我不明白如何找到m=√n。我想如下。

(n/m)+m-1=0; 
(n/m)+m=1; 
n+m^2=m; 
n=m-m^2. 

但这是如何成为m = m=√n

Answer 1

我假设你想找到的最低任何n。

(n/m)+m-1 

最小值是在坡度为0

所以区分对于表达对m：

d/dm (n/m)+m-1 = 1-n/m^2 

和解决1-n/m^2 = 0给你m = sqrt(n)