乘法的优化
暴力的乘法复杂度是\(O(n^2)\)的。
如果两个\(n\)位数\(x,y\)相乘(我们保证\(n\)是2的幂),那么我们按位把\(x\)分成\(x_L,x_R\)两半,\(y\)分成\(y_L,y_R\),使得\(x=x_L \cdot 2^{n/2}+x_R,y=y_L \cdot 2^{n/2}+y_R\)。那么\(xy=x_Ly_L \cdot 2^n + (x_Ly_R+x_Ry_L)\cdot 2^{n/2}+x_Ry_R\)。加法和乘以2的幂次都是\(O(n)\)的,而余下的乘法可以递归的完成。设两个\(n\)位数的乘法所需时间是\(T(n)\)。那么有递推关系\(T(n)=4T(n/2)+O(n)\)。可以画出递归树解得\(T(n)=O(n^2)\)。
利用Guass's Trick,我们可以进行优化。我们可以计算出\(x_ly_L,x_Ry_R\),再计算出\((x_L+x_R)(y_L+y_R)\),用第三个数减去前两个数就可以得到交叉项。这样四次乘法就被优化到了三次。此时\(T(n)=3T(n/2)+O(n)\)。这时解变成了\(T(n)=O(n \cdot \left(\dfrac{3}{2}\right)^{\log n})=T(3^{\log_2 n})=T(n^{\log_2 3})\approx T(n^{1.59})\)
主定理
从上述例子中可以发现,分治算法的复杂度分析一般式为:
\(T(n)=aT(n/b)+O(n^d)\)
其中假设\(n\)是\(b\)的幂。
我们依然画出递归树。得到(\(k=\log_b n\))
\(T(n)=O\left(n^d+a \cdot \dfrac{n^d}{b^d}+a^2 \cdot \dfrac{n^d}{(b^2)^d}+\cdots+a^k \cdot \dfrac{n^d}{(b^k)^d}\right)\)
这是等比数列,公比为\(\dfrac{a}{b^d}\)。因此需要分类讨论。
当\(a>b^d\)时,\(T(n)=O(n^d \cdot \dfrac{\frac{a^k}{b^{dk}}-1}{\frac{a}{b^d}-1})=O(a^{\log_b n})=O(n^{\log_b a})\)
当\(a=b^d\)时,\(T(n)=O(n^d \cdot k)=O(n^d \cdot \log_b n)=O(n^d \log n)\)
当\(a<b^d\)时,\(T(n)=O(n^d \cdot \dfrac{1-\frac{a^k}{b^{dk}}}{1-\frac{a}{b^d}})=O(n^d)\)
排序
归并排序满足\(T(n)=2T(n/2)+O(n)\),解得\(T(n)=O(n \log n)\)。我们可以证明基于比较的排序算法不可能比这更优。
考虑给一个全排列\(\sigma\)排序,第一次比较\(\sigma_{i_1},\sigma_{j_1}\)两个元素。\(\sigma\)分为两类,一类满足\(\sigma_{i_1}<\sigma_{j_1}\),一类满足\(\sigma_{i_1}>\sigma_{j_1}\);在每一类中,又可以分为\(\sigma_{i_2}<\sigma_{j_2}\)和\(\sigma_{i_2}>\sigma_{j_2}\)。如果把这种分类看成一颗二叉树的话,它的叶节点就有\(n!\)个。排序算法的优劣就在于怎么选择每一次的\(i_k,j_k\),因为这决定了二叉树的形态。为了让排序算法最优秀,一定要让最坏的也就是深度最大的叶节点的深度尽量小。因此这应当尽量是一颗平衡树(满二叉树),此时最大深度为\(\log_2 (n!)\)。根据Stirling's Formula,\(n! \sim \sqrt{2n\pi}\left(\dfrac{n}{e}\right)^n\),因此\(O(\log n!)=O(n \log n)\)。可见任何排序算法的比较次数都不可能小于\(O(n \log n)\)这个量级。
Medians
求中位数的复杂度是可以优于排序的复杂度的。我们每次随机选择一个数\(v\),把小于\(v\)的和大于\(v\)的挑出来,转化成在新的数组里找第\(k\)小的问题。我们不停随机这个\(k\),直到挑到\(v\)的排名在\(1/4\)到\(3/4\)之间。由于概率为\(1/2\),随机次数的期望是\(1/2+1/4+\cdots=2\)。因此可以写出期望复杂度\(T(n)=T(3/4n)+O(n)\),解得\(T(n)=O(n)\)。
在理论计算机导论中,还学过一个并不随机的算法Median of Medians,复杂度是\(T(n)=T(\dfrac{n}{5})+T(\dfrac{7n}{10})+O(n)\),解得\(T(n)=O(n)\)。
标签:log,cdot,dfrac,复杂度,分治,排序,sigma From: https://www.cnblogs.com/qixingzhi/p/17207353.html