深圳福步外贸论坛seo网络优化师招聘
原帖
最近校内比较忙，更新缓慢，致歉。
这里函数每次都需要遍历 h h h 和 m m m 之间的数（复杂度 O ( n ) O(n) O(n)），所以和 solve1 略有不同。仍然假设 T ( n ) \operatorname{T}(n) T(n) 表示 m − h + 1 = n m-h+1=n m−h+1=n 时的复杂度。
T ( n ) = 2 × T ( n / 2 ) + n = 2 × ( 2 × T ( n / 4 ) + n / 2 ) + n = 4 × T ( n / 4 ) + 2 n \operatorname{T}(n)=2\times\operatorname{T}(n/2)+n=2\times(2\times\operatorname{T}(n/4)+n/2)+n=4\times\operatorname{T}(n/4)+2n T(n)=2×T(n/2)+n=2×(2×T(n/4)+n/2)+n=4×T(n/4)+2n
总结一下规律，就是： T ( n ) = 2 k × T ( n / 2 k ) + k n \operatorname{T}(n)=2^k\times\operatorname{T}(n/2^k)+kn T(n)=2k×T(n/2k)+kn，这里 k = l o g 2 n k=log_2n k=log2n。（假设 k k k 是下取整的，造成的误差在计算时间复杂度时可忽略不计）。
T ( n ) = 2 k + n k = n + n k \operatorname{T}(n)=2^{k}+nk=n+nk T(n)=2k+nk=n+nk，相当于 O ( n l o g n ) O(nlogn) O(nlogn) 的复杂度。