algorithm - 跳转搜索中如何找到跳转 block 大小的最优值？

Question

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

我明白 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)