分治算法的时间复杂度

这周末我把分治算法重新学了一下。

假设某问题的输入是一个长度为n的数组,解决这个问题所需花的时间是T(n)

假设分治算法总是把原问题分解成q个规模为n/2的子问题,划分和merge所需的时间是f(n)

那么 T(n)=qT(n/2)+f(n)

\(T(n)=q^2T(\frac{n}{4})+qf(\frac{n}{2})+f(n)\)

于是有\( T(n) = q^kT(\frac{n}{2^k})+f(n)+qf(\frac{n}{2})+q^2f(\frac{n}{4})+...+q^{k-1}f(\frac{n}{2^{k-1}}) \)

令 \( 2^k = n\) , \(r=\log_2{q}\) 则\(q^k = n^r \)

则:

\( T(n) = n^rT(1)+f(n)+qf(\frac{n}{2})+q^2f(\frac{n}{4})+...+q^{k-1}f(2) \)

下面分析几种特例:

f(n)是常数

假设f(n)是常值函数,如f(n)=c。则

当q大于1:

\( T(n) = n^rT(1)+ c\frac{q^k-1}{q-1}=O(n^r) \)

当q等于1:

\( T(n) = T(1)+ c\log_2{n}=O(\lg n) \) 对应算法:二分查找、单峰数列求最大值。

f(n)是一阶线性函数

假设f(n)是一阶线性函数,如f(n)=cn,则

当q等于1:

\( T(n) = T(1)+cn+\frac{cn}{2}+\frac{cn}{4}+...+\frac{cn}{2^{k-1}}=T(1)+2cn=O(n) \)。

当q等于2:

\( q^{k-1}f(\frac{n}{2^{k-1}}) = 2^{k-1}\frac{cn}{2^{k-1}}=cn \)

\( T(n) = nT(1)+ n\log_2{n} =O(n\lg n) \),对应算法:merge sort。

当q大于2:

\( T(n) = O(n^r) \) 对应算法:大整数乘积。

嗯,于是类似的可推出,只要f(n)是多项式,那么原问题就是多项式时间可解的。

当输入集是二维或高维时,分析工作就复杂很多。等我遇到对应的问题,再具体分析吧。

先列一个:Longest Common Subsequence(LCS)问题。假设两个字符串,长度分别是m和n。它们的LCS的长度已知,求这个序列本身。那么在原来的LCS求解矩阵中,找到第m/2行,用它把原矩阵劈成两半,然后在这一行找到第j个子元素,那么如果有T(m,n) = T(m/2,j) + T(m/2,n-j)+cmn,就可推出T(m,n) <= 2cmn。

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥