分治法

一、主体思想

  • 将问题\(T(N)\)分解为\(a\)个子问题
  • 通过递归的方法解决子问题,时间复杂度为\(T(\frac{N}{b})\)
  • 将子问题的解合并,得到原始问题的解,时间复杂度为\(f(N)\)

一般的递归:\(T(N) =aT(\frac{N}{b})+f(N)\)

降低算法时间的关键:\(f(N)\)

二、分析算法的时间复杂度

2.1 asymptotic analysis 渐进分析

  • 省略常数项
  • 省略低阶项

2.2 Random Access Model–RAM:随机访问模式

单元操作,如**+、-、*、/、=、内存读取**,所需时间为常数

三、Closest Points Problems

3.1 问题描述

给定n个点,求这n个点两两之间的最短欧氏距离

3.2 解决思路

  • n个点分成两组,每组n/2个点,满足\(x_1\leq x_2\leq...\leq x_n\),记为\(L_x,R_x\)
  • 递归解决两组的最短距离
  • 将子问题合并为原问题

3.3 合并操作

\(\delta = min(CPP(L_x),CPP(R_x))\),将\(L_x,R_x\)中,与中心距离\(<\delta\)的点分别取出,记为\(T_l,T_r\),令\(T=T_l \bigcup T_r\)

image-20240416200700159

假设\(\exist P_l\in S_l,P_r \in S_r\),使得\(dist(P_l,P_r)=D<\delta\),则可以得出以下性质

性质1:\(P_l\in T_l,P_r\in T_r\),即这两点一定在中线两侧

​ 如果\((P_l,P_r)\)属于同一侧,表明在\(T_l\)\(T_r\)的一侧能够找到两个点,使其距离<\(\delta\),与\(\delta\)的定义矛盾

性质2:任意一对\(P_l,P_r\),一定存在一个以中线为轴的\(2\delta*\delta\)的矩形区域,将它们包含在内

​ 假设\(P_l,P_r\)没有位于该区域,以图中所示的红线相连的两个点为例

​ 可见,其距离一定会大于\(\delta\),即\(dist(P_l,P_r)>\delta\),与\(dist(P_l,P_r)=D<\delta\)矛盾

image-20240416200713213

性质3:以中线为轴的\(2\delta*\delta\)的矩形区域内至多包含T中的6个点,且\(T_l\)\(T_r\)中各至多有4个

​ 取\(2\delta*\delta\)矩形的右半边出来,即为\(\delta*\delta\)的小矩形

​ 假设已经有4个点分布在这个矩形的四个角,那么矩形内部无法再有任何点的存在。因为这个小矩形\(\in T\),假设如果小矩形内还有一个红点,令其与其余四点的距离均最远,那么红点必定位于小矩形的中心位置,距离其余四点的距离为\(\frac{\sqrt{n}}{2}\delta\),与\(\delta\)的定义矛盾。

​ 因此,左右两边的小矩形最多有4个点。而由于两个小矩形会有两个点重合,因此\(2\delta*\delta\)的矩形区域内至多有6个点

image-20240416200722688

根据上述性质,我们可以得出:

(1)如果把\(T\)中的点按照\(Y\)坐标升序排序,任取一点\(T[i]\)\(T[i+7]\)\(T[i]\)的距离一定超过\(\delta\)

(2)如果把\(T_l\)中的点按照\(Y\)坐标升序排序,任取一点\(T_l[i]\)\(T_l[i+5]\)\(T_l[i]\)的距离一定超过\(\delta\)\(T_r\)同理

合并的具体操作

  1. \(\delta = min(CPP(L_x),CPP(R_x))\),将\(L_x,R_x\)中,与中心距离\(<\delta\)的点分别取出,记为\(T_l,T_r\),令\(T=T_l \bigcup T_r\)
  2. \(T\)中的点按照\(Y\)坐标升序排列,对每一个\(T[i]\),计算其与\(T[i+1] →T[i+6]\)的距离,并更新答案

四、递归树 Recursion-tree method

  • 树的每一个节点,表示该节点消耗的时间
  • 整个问题消耗的时间,为所有节点加起来的结果

image-20240416200742324

例:\(T(n)=2T(\frac{n}{2})+\frac{n}{log\ n}\rightarrow O(nlog\ log\ n)\)

\[ \begin{aligned} T(n)&=2T(\frac{n}{2})+\frac{n}{log\ n} \\ &=\frac{n}{log\ n}+2*\frac{n/2}{log\ n/2}+...+2^k*\frac{n/2^k}{log\ n/2^k} \\ &=\sum_{k=0}^{log\ n}2^k*\frac{n/2^k}{log\ n/2^k} \\ &=n*\sum_{k=0}^{log\ n} \frac{1}{log\ n/2^k} \\ &=n*\sum_{k=0}^{log\ n} \frac{1}{log\ n - k*log\ 2} \\ &=n*\sum_{k=0}^{log\ n}\frac{1}{log\ n - k} \\ &=n*\sum_{k=0}^{log\ n}\frac{1}{k} \\ &=n*(1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{log\ n})\\ &=n*log log\ n \end{aligned} \]

例:\(T(n)=8*T(\frac{n}{2})+O(1),n^2\geq m; m,n^2< m \rightarrow O(\frac{n^3}{\sqrt m})\)

建立递归树:

  • 树的每一个节点的时间复杂度为\(O(1)\)
  • 树的每一层有\(8^k\)个节点
  • \(n^2>m \rightarrow \frac{n}{\sqrt m}>1\),因此树有\(log\frac{n}{\sqrt m}\)

时间复杂度为:\(8^{log\frac{n}{\sqrt m}}*m=O(\frac{n^3}{\sqrt m})\)

例:\(T(n)=T(\frac{n}{6})+T(\frac{7n}{9})+O(n) \rightarrow O(n)\)

\(T(n)=2T(\frac{n}{6}) + O(n)\)\(a=2,b=6,N^{log_ba}=N^{log_62}<N\) => \(T(N)=O(N)\)

\(T(n) = 2T(\frac{7n}{9}) + O(n)\)\(a=2,b=\frac{9}{7},N^{log_ba}=N^{log_{\frac{9}{7}}2}>N\) => \(T(N)=O(N^{log_{\frac{9}{7}}2})=O(N^{2.75})\)

五、主定理

5.1 f(N)直接给出

\(T(N)=aT(\frac{N}{b})+f(N)\),则

  • \(f(N)<O(N^{log_ba})\),则\(T(N)=\Theta(N^{log_ba})\)
  • \(f(N)=O(N^{log_ba})\),则\(T(N)=\Theta(f(N)*log_bN)\)
  • \(f(N)>O(N^{log_ba})\),则\(T(N)=\Theta(f(N))\)

5.2 f(N)为递归表示

\(T(N)=aT(\frac{N}{b})+f(N)\),则

  • \(f(N)<af(\frac{N}{b})\),则\(T(N)=\Theta(N^{log_ba})\)
  • \(f(N)=af(\frac{N}{b})\),则\(T(N)=\Theta(f(N)*log_bN)\)
  • \(f(N)>af(\frac{N}{b})\),则\(T(N)=\Theta(f(N))\)

5.3 f(N)直接给出

\(T(N)=aT(\frac{N}{b})+\Theta(N^k log^p N)\),且\(a\geq 1,b>1,p\geq 0\),则

  • \(a>b^k\),则\(T(N)=O(N^{log_b a})\)
  • \(a=b^k\),则\(T(N)=O(N^k log^pN*log_bN)\)
  • \(a<b^k\),则\(T(N)=O(N^k log^{p}N)\)

例题

image-20240416200924486 \[ \begin{aligned} &设m=log\ n,则2^m=n \rightarrow T(2^m)=2T(2^{\frac{m}{2}})+m \\ &设G(m)=T(2^m),则 \\ &原式转化为:G(m)=2G(\frac{m}{2})+m=O(mlog\ m)\\ &又\because m=log\ n\\ &\therefore T(n)=O(log\ n*log\ log\ n) \end{aligned} \]