分治法

分治模式
分解（Divide）：将原问题分解成一系列子问题；
解决（Conquer）：递归地解各子问题。若子问题足够小，则直接求解；
合并（Combine）：将子问题的结果合并成原问题的解。
Ex.Merge Sort, Binary Search

一些举例

powering the number

given a number x, and integer , compute x^n
Native algorithm: Θ(n)
Divide and conquer:
T(n)=Θ(lgn)

Fibonacci numbers

Native recursive algorithm: Time
recursive squaring: 转化为矩阵：

Matrix Multiplition

Input: A=[aij], B=[b_ij]
Output: C=[c_ij] = A*B, 
standard algorithm: Θ(n^3)

for i=1 to n
    do for j=1 to n
      do c_ij = 0
    for k=1 to n
        c_ij = a_ik * b_kj + c_ij
end

IDEA:nn matrix = 22 blank matrix of n/2 n/2 sub matrix
need 8 recursive calls: T(n) = 8T(n/2)+Θ(n^2) = Θ(n^3)
Strassen’s algorithm:
*IDEA:reduce recursive calls to 7 recursive calls

二叉树遍历及相关特性

计算二叉树高度

public int TreeHeight(TreeNode root){
    if(root==null){
      return -1;
  }
  return Math.max(TreeHight(root.left),TreeHeight(root.right))+1;
}

二叉树的遍历
前序遍历、中序遍历、后序遍历

大整数乘法

Native aglorithm recursive: need 4 recursive calls;
change to 3 recursive calls;

最近点对问题

EfficientClosestPair(P,Q)
if n<=3
    return the minimal distance found by bruce-force aglorithm
else
    copy the first (n/2)向上取整 points of P to array Pl
  copy the same (n/2) points from Q to arrays Ql
  copy the remaining (n/2)向下取整 points of P to array Pr
  copy the same (n/2)points from Q to array Qr
  dl = EfficientClosestPair(Pl,Ql)
  dr = EfficientClosestPair(Pr,Qr)
  d = min(dl,dr)
  m = P[(n/2)-1].x
  copy all the points of Q for which |x-m|<d into array S[0...num-1]
  dminsq = d^2
  for i=0 to num-2 do
      k = i+1
    while k<=num-1 and (S[k].x)-S[i].x)^2<dminsq
        dminsq = min((S[k].x-S[i].x)^2+(S[k].y-S[i].y)^2,dminsq)
      k=k+1
 return sqrt(dminsq)