为什么跳转搜索（Jump Search）的最优步长m取值为√n？

首先明确前提：跳转搜索是仅适用于有序数组的查找算法，所有推导均基于该前提。

步长选择对时间复杂度的影响 #

跳转搜索的执行逻辑分为两步：

1. 按固定步长m从数组头部向后跳跃，直到找到第一个大于目标值的元素，确定目标值所在的长度为m的子块
2. 在对应子块内做线性搜索，查找目标值

最坏情况下的总操作数由两部分组成：

• 跳跃次数：最多为n/m次（n为数组总长度，最坏情况要跳完所有块）
• 块内线性搜索次数：最多为m-1次（最坏情况目标值在块的最后一位，或者不存在）

因此最坏时间复杂度的表达式为：f(m) = n/m + m
基于该公式可以得出步长对复杂度的影响：

• 步长过小：极端情况m=1时，f(m)=n/1 + 1 = O(n)，退化为普通线性搜索
• 步长过大：极端情况m=n时，f(m)=n/n + n = O(n)，同样退化为线性搜索
  只有步长取值适中时，才能让跳跃次数和块内搜索次数的总和达到最小，得到O(√n)的最优时间复杂度。

最优步长为√n的推导 #

求f(m) = n/m + m的最小值，可以用两种方法推导：

方法1：均值不等式 #

对于两个正实数a和b，有不等式a + b ≥ 2√(a*b)，等号成立当且仅当a = b。
代入a = n/m，b = m，可得：
n/m + m ≥ 2√(n/m * m) = 2√n
等号成立条件为n/m = m，即m² = n，m = √n（步长为正，舍去负解）。

方法2：求导找极值 #

对f(m)关于m求导：
f'(m) = -n/m² + 1
令导数等于0（极值点导数为0），解得：
m² = n，即m = √n
代入原式可得此时总操作数为2√n，是函数的极小值，也是最小值。

示例验证 #

比如数组长度n=100，最优步长为10，最坏总操作数为100/10 + 10 = 20次；如果步长取5，总操作数为20 +5=25次；步长取20，总操作数为5+20=25次，均大于最优值，符合推导结果。

内容的提问来源于stack exchange，提问作者chai