*课程框架树# Advanced DSSearchAVL RB B+ [App]Inverted file index heapLeftist Skew Binomial Fibonacci Paring AlgorithmDesign TechniqueBasicGreedy DP Devide and Conquer Backtracking Opti.Approximation Local search miscRandomized *Parallel External Sorting Analysis TechniquePC vs NPC Amortized Analysis Backtracking# 补充定义
S i S_i S i i i i game tree 又叫决策树 例一:八皇后
S i { 1 ⋯ 8 } x i ≠ x j ( i ≠ j ) ∣ ( x i − x j ) ( i − j ) ∣ ≠ 1 ( i ≠ j ) S_i\{1\cdots 8\}\\ x_i\neq x_j(i\neq j)\\ \left|\frac{(x_i-x_j)}{(i-j)}\right|\neq 1(i\neq j) S i { 1 ⋯ 8 } x i = x j ( i = j ) ( i − j ) ( x i − x j ) = 1 ( i = j ) Solution 1: Q . . . . . . . . . . . . . Q . . . . . Q . . . . . . . . . . Q . Q . . . . . . . . . Q . . . . . . . . . Q . . . . Q . . . . . Solution 2: Q . . . . . . . . . . . . . Q . . . . Q . . . . . . . . . Q . . . . . . . . . Q . Q . . . . . . . . . . Q . . . . . Q . . . . . Solution 3: Q . . . . . . . . . . . . Q . . . . . . . . . Q . . Q . . . . . . . . . . . Q . . . . Q . . . . . Q . . . . . . . . . . Q . . . Solution 4: Q . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . . . . . . . Q . . Q . . . . . . . . . Q . . . . (...) 另外一个例子的阶段 设计则没有那么显然
eg2. Turnpike Reconstruction
S 1 = [ 1 , n ] S i − 1 = S i − { l i } ∨ S i − 1 = S i − { r i } S_1=[1,n] \\S_{i-1} =S_i-\{l_i\}\vee S_{i-1}=S_i-\{r_i\}\\ S 1 = [ 1 , n ] S i − 1 = S i − { l i } ∨ S i − 1 = S i − { r i } 每个阶段的决策并不好用变量来写
具体而言我们考虑用递归的方式定义这个过程
R e c o n s t r u c t i o n ( X , D , N , l , r ) \mathrm{Reconstruction}(X,D,N,l,r) Reconstruction ( X , D , N , l , r )
表示我们已经将[ 1 , l − 1 ] , [ r + 1 , N ] [1,l-1],[r+1,N] [ 1 , l − 1 ] , [ r + 1 , N ] D D D X [ l → r ] X[l\to r] X [ l → r ] 能否 产生可行解的过程
后续递归显然，剪枝即为，我们在选左和选右缩减时需要提前检查是否出现了未知的距离
Alpha-Beta prunning# Minmax Strategy :以tic-tac-toe为例，A与B分别持有最大化/，最小化某一收益的前提目标，则我们可以对game tree奇偶分层分别实现最值Alpha-Beta punning :基于该想法卡上下界（开始进入有奇偶两种），可以在实践中缩减规模到O ( N ) \mathcal O(\sqrt N) O ( N ) N N N Divide and Conquer# Definition# Divide ：将问题规模切割成结构相似的子问题Conquer : 递归解决子问题Combine : 总问题的解决依赖子问题的结果，同时也需要合并Closest Points Problem# n n n
算法描述
按照x x x 处理两侧的最近点对和跨点集的最近点对 假设两侧的结果为δ \delta δ [ x 0 − δ , x 0 + δ ] [x_0-\delta,x_0+\delta] [ x 0 − δ , x 0 + δ ] 任意选取范围内一个点，则可更新区域变为[ x 0 − δ , x 0 + δ ] × [ y 0 , y 0 − δ ] [x_0-\delta,x_0+\delta]\times [y_0,y_0-\delta] [ x 0 − δ , x 0 + δ ] × [ y 0 , y 0 − δ ] 可以证明最多只有6个不重合的 点 则复杂度为T ( N ) = 2 T ( N 2 ) + O ( N ) = O ( N log N ) T(N)=2T(\frac{N}{2})+\mathcal O(N)=\mathcal O(N\log N) T ( N ) = 2 T ( 2 N ) + O ( N ) = O ( N log N )
复杂度分析# T ( N ) = a T ( N b ) + f ( N ) , a , b ∈ Z + T(N)=aT(\frac{N}{b})+f(N),a,b\in \mathbb Z^+ T ( N ) = a T ( b N ) + f ( N ) , a , b ∈ Z + 迭代求解法/递归树法# T ( N ) = . . . = c N l e a v e s ⏟ c o n q u e r + ∑ n o d e i n o n − l e a f − n o d e s f ( N n o d e i ) ⏟ c o m b i n e T(N)=...=\underbrace{c N_{leaves}}_{conquer}+\underbrace{\sum_{node_i}^{non-leaf-nodes}f(N_{node_i})}_{combine} T ( N ) = ... = co n q u er c N l e a v es + co mbin e n o d e i ∑ n o n − l e a f − n o d es f ( N n o d e i ) 以T ( N ) = 2 T ( N / 2 ) + O ( N ) T(N)=2T(N/2)+\mathcal O(N) T ( N ) = 2 T ( N /2 ) + O ( N )
T ( N ) = 2 k T ( N 2 k ) + k O ( N ) T(N)=2^kT(\frac{N}{2^k})+k\mathcal O(N) T ( N ) = 2 k T ( 2 k N ) + k O ( N ) k → ∞ , 2 k T ( N 2 k ) → O ( N ) k \to \infty ,2^kT(\frac{N}{2^k})\to \mathcal O(N) k → ∞ , 2 k T ( 2 k N ) → O ( N )
这个基于N 0 ∈ [ 1 , σ ) N_0\in [1,\sigma) N 0 ∈ [ 1 , σ ) T ( N 0 ) = O ( 1 ) T(N_0)=\mathcal O( 1) T ( N 0 ) = O ( 1 )
补充例子
T ( N ) = 3 T ( N 4 ) + Θ ( N 2 ) T(N)=3T(\frac{N}{4})+\Theta (N^2) T ( N ) = 3 T ( 4 N ) + Θ ( N 2 ) 展开有
T ( N ) = ∑ i = 0 log 4 N − 1 ( 3 16 ) i c N 2 + Θ ( N log 4 3 ) < ∑ i = 0 ∞ ( 3 16 ) i c N 2 + Θ ( N log 4 3 ) = c N 2 1 − 3 16 + Θ ( N log 4 3 ) = O ( N 2 ) \begin{align*} T(N)&=\sum _{i=0}^{\log_4N-1}\left(\frac{3}{16}\right)^i cN^2+\Theta (N^{\log _43}) \\&<\sum_{i=0}^\infty \left(\frac{3}{16}\right)^icN^2+\Theta (N^{\log _4 3})\\&=\frac{cN^2}{1-\frac{3}{16}}+\Theta (N^{\log_4 3})=\mathcal O(N^2) \end{align*} T ( N ) = i = 0 ∑ l o g 4 N − 1 ( 16 3 ) i c N 2 + Θ ( N l o g 4 3 ) < i = 0 ∑ ∞ ( 16 3 ) i c N 2 + Θ ( N l o g 4 3 ) = 1 − 16 3 c N 2 + Θ ( N l o g 4 3 ) = O ( N 2 ) 这个过程a = 3 , b = 4 , f ( n ) = Θ ( n 2 ) a=3,b=4,f(n)=\Theta (n^2) a = 3 , b = 4 , f ( n ) = Θ ( n 2 )
代换法/归纳法# 上面这个你猜一下带入即可
T(N) = d N log N − d N ( log 2 3 − 2 3 ) + c N ≤ d N log N f o r d ≥ c / ( log 2 3 − 2 3 ) \begin{gathered} \text{T(N)} \\ =dN\log N-dN(\log_23-\frac23)+cN\leq dN\log N \\ ford\geq c/(\log_23-\frac23) \end{gathered} T(N) = d N log N − d N ( log 2 3 − 3 2 ) + c N ≤ d N log N f or d ≥ c / ( log 2 3 − 3 2 ) Master Method# 对于形如T ( N ) = a T ( N / b ) + f ( N ) T(N)=aT(N/b)+f(N) T ( N ) = a T ( N / b ) + f ( N ) f ( N ) = O ( N ( log b a ) − ε ) f(N)=O(N^{(\log_ba)-\varepsilon}) f ( N ) = O ( N ( l o g b a ) − ε ) ε > 0 \varepsilon>0 ε > 0 T ( N ) = Θ ( N log b a ) ; T(N)=\Theta(N^{\log_ba}); T ( N ) = Θ ( N l o g b a ) ; f ( N ) = Θ ( N log b a ) f(N)=\Theta(N^{\log_ba}) f ( N ) = Θ ( N l o g b a ) T ( N ) = Θ ( N log b a log N ) ; T(N)=\Theta(N^{\log_ba}\log N); T ( N ) = Θ ( N l o g b a log N ) ; f ( N ) = Ω ( N ( log b a ) + ε ) f(N)=\Omega(N^{(\log_ba)+\varepsilon}) f ( N ) = Ω ( N ( l o g b a ) + ε ) ε > 0 \varepsilon>0 ε > 0 a f ( N b ) < c f ( N ) af(\frac Nb)<cf(N) a f ( b N ) < c f ( N ) c < 1 c<1 c < 1 ∀ N > N 0 \forall N>N_0 ∀ N > N 0 T ( N ) = Θ ( f ( N ) ) ; T(N)=\Theta(f(N)); T ( N ) = Θ ( f ( N )) ;
注意
Merge sorta = b = 2 a=b=2 a = b = 2 T ( N ) = O ( N log N ) T(N)=\mathcal O(N\log N) T ( N ) = O ( N log N ) a = b = 2 , f ( N ) = N log N a=b=2,f(N)=N\log N a = b = 2 , f ( N ) = N log N Proof# Case1# f ( N ) = O ( N log b a − ε ) f(N)=\mathcal O(N^{\log_ba-\varepsilon}) f ( N ) = O ( N l o g b a − ε ) T ( N ) = Θ ( N log b a ) ; T(N)=\Theta(N^{\log_ba}); T ( N ) = Θ ( N l o g b a ) ;
Case2# f ( N ) = ( N log b a ) f(N)=\mathcal(N^{\log_ba}) f ( N ) = ( N l o g b a ) T ( N ) = Θ ( N log b a log N ) ; T(N)=\Theta(N^{\log_ba}\log N); T ( N ) = Θ ( N l o g b a log N ) ;
证明：前面的部分和情况一的类似，我们通过相同的步骤得到相同的求和式：
T ( N ) = Θ ( N log b a ) + ∑ j = 0 ( log b N ) − 1 a j f ( N b j ) T(N)=\Theta(N^{\log_ba})+\sum_{j=0}^{(\log_bN)-1}a^jf(\frac N{b^j}) T ( N ) = Θ ( N l o g b a ) + ∑ j = 0 ( l o g b N ) − 1 a j f ( b j N )
而我们有条件f ( N ) = Θ ( N log b a ) f(N)=\Theta(N^{\log_ba}) f ( N ) = Θ ( N l o g b a )
T ( N ) = Θ ( N log b a ) + ∑ j = 0 ( log b N ) − 1 a j Θ ( ( N b j ) log b a ) = Θ ( N log b a ) + Θ ( N log b a × ∑ j = 0 ( log b N ) − 1 ( a b log b a ) j ) = Θ ( N log b a ) + Θ ( N log b a × log b N ) = Θ ( N log b a log N ) \begin{aligned}T(N)&=\Theta(N^{\log_ba})+\sum_{j=0}^{(\log_bN)-1}a^j\Theta\left(\left(\frac N{b^j}\right)^{\log_ba}\right)\\&=\Theta(N^{\log_ba})+\Theta\left(N^{\log_ba}\times\sum_{j=0}^{(\log_bN)-1}\left(\frac a{b^{\log_ba}}\right)^j\right)\\&=\Theta(N^{\log_ba})+\Theta\left(N^{\log_ba}\times\log_bN\right)\\&=\Theta(N^{\log_ba}\log N)\end{aligned} T ( N ) = Θ ( N l o g b a ) + j = 0 ∑ ( l o g b N ) − 1 a j Θ ( ( b j N ) l o g b a ) = Θ ( N l o g b a ) + Θ N l o g b a × j = 0 ∑ ( l o g b N ) − 1 ( b l o g b a a ) j = Θ ( N l o g b a ) + Θ ( N l o g b a × log b N ) = Θ ( N l o g b a log N )
至此，情况二证明完毕。
Case3# f ( N ) = f(N)= f ( N ) =
where a ≥ 1 , b > 1 \textbf{where }a\geq 1, b> 1 where a ≥ 1 , b > 1 p ≥ 0 p\geq0 p ≥ 0
T ( N ) = { O ( N log b a ) i f a > b k O ( N k log p + 1 N ) i f a = b k O ( N k log p N ) i f a < b k \begin{gathered}T(N)=\begin{cases}\:O(N^{\log_ba})&\mathrm{if~}a>b^k\\\:O(N^k\log^{p+1}N)&\mathrm{if~}a=b^k\\\:O(N^k\log^pN)&\mathrm{if~}a<b^k\end{cases}\end{gathered} T ( N ) = ⎩ ⎨ ⎧ O ( N l o g b a ) O ( N k log p + 1 N ) O ( N k log p N ) if a > b k if a = b k if a < b k
