网站备案才能使用360搜图片识图

原帖
最近校内比较忙，更新缓慢，致歉。

这里函数每次都需要遍历 $h$ 和 $m$ 之间的数（复杂度 $O(n)$），所以和 solve1 略有不同。仍然假设 $T(n)$ 表示 $m-h+1=n$ 时的复杂度。
$T(n)=2\times T(n/2)+n=2\times (2\times T(n/4)+n/2)+n=4\times T(n/4)+2n$
总结一下规律，就是：$T(n)=2^k\times T(n/2^k)+kn$，这里 $k=lo{g}_{2}n$。（假设 $k$ 是下取整的，造成的误差在计算时间复杂度时可忽略不计）。
$T(n)=2^k+nk=n+nk$，相当于 $O(nlogn)$ 的复杂度。