算法(2)-递归式时间复杂度求解与分治法

要点

• 递归式T(n)求解
  • 代换法*
  • 迭代法*
  • 递归树
  • 主定理 Master (core)
• 分治策略
  • Insert Sort 插入排序 VS Merge Sort 归并排序
  • 最大子数组
  • 矩阵Strassen乘法(*)
  • 多数问题 Majority Problem

复习

• 输入规模: 假设输入了一个大小为n的十进制数, 在计算机中所占用的x位, 即2^x = n
  因此, 占用内存位数x (单位: bit) = lgn (bit)
  因此, 我们一般都说大小为n的十进制数的在计算机中表现为C*lgn个bit 输入规模 (C = Constant)

递归式求解

• 代换法: 猜; 猜了以后用数学归纳法证明;
  • 猜测T(n) = nlgn + n;
  • 假设T(k) = k*logk + k; (k<n就可以)
  • 验证T(n) 状况, 代入T(n) = 2T(n/2)+n来求解;
  • 例题2: Tn=T(n/2)up+T(n/2)down +1 (为什么这里不能丢掉1? 因为下面的要求!)
  • 避免陷阱: 数学归纳法的原理是推理链条, 小项目会累积, 必须严格证明, 不能丢掉低阶级项目;
  • 变量替换: sqrt(n) 用m替换; 形式上更容易求解;
  • 对更小的值做更强的假设;
• 迭代法
  • 不断地把递归式子展开, 对各个展开项目求和, 迭代法对代数能力要求较高;
  • 难点: 迭代次数求解, 级数求和;
  • 弄明白一个除以2, 一个加1的关系;
• 递归树方法
• 主方法
  • T(n) = a*T(n/b) + f(n);
  • 注意n*logn和n^1.0001对比仍然是后者大

分治算法

备注: 实际C语言中数组下标为a[0]~a[length-1], pseudo code里面我们按照日常习惯, 从1~length

注: 插入排序不是分治算法, 只是这里一起写, 和merge-sort做比较.

Insert-Sort()
for i = 2 to A.length
  key = A[i]    //insert key to sequence A[1~i-1]
  j = i-1
  while j>0 && A[j]>key
    A[j+1] = A[j]    //把值向后移动一位
    j--
  A[j+1] = key    //当发生A[j]<=key的时候, 让key的值占据A[j+1]位置, 注意A[j+2]已经安全存好了原先A[j+1]的值

最典型的Divide and Conquer: Merge Sort

//@p: prior;
//@r: rear;
Merge-Sort(A, p, r)
if p<r    //when p == r, the following lines will not execute
  q = floor((p+r)/2)
  Merge-Sort(A, p, q)
  Merge-Sort(A, q+1, r)
  Merge(A, p, q, r)

Merge(A, p, q, r) {
n1 = q-p+1
n2 = r-q
let L[n1+1] and R[n2+1] be new arrays
for (i = 1 to n1) 
    L[i] = A[p-1+i]
for (j = 1 to n2)
    R[j] = A[q+j] 
L[n1+1] = 99999    //代表无穷大的哨兵牌, 最后不输出
L[n2+2] = 99999
i = 1, j = 1
for (k=p to r)
    if (L[i]<R[j])
        A[k] = L[i]
        i++
    else 
        A[k] = R[j]
        j++
}

时间复杂度分析:
(1)写出递归式: T(n) = 2T(n/2)+Θ(n)
(2)使用主定理: 计算n^log(b下a上) = n = f(n) , 所以T(n) = nlgn

• 最大子数组;

/*主算法: 找最大子数组*/
//low表示左边端点, high右侧端点, A是数组
Find-Maximum-SubArray(A, low, high)
if (low == high) 
    return (low, high, A[low])
mid = floor((low+high) / 2)  //下中位数
(left-low, left-high, left-sum) = Find-Maximum-SubArray(A, low, mid)
(right-low, right-high, right-sum) = Find-Maximum-SubArray(A, mid+1, high)  //记得是[mid+1, high] 左侧端点要mid+1
(cross-low, cross-high, cross-sum) = Find-Max-Crossing-SubArray(A, low, mid, high) 
if (left-sum>right-sum and left-sum>cross-sum) 
    return (left-low, left-high, left-sum)
else if (right-sum>left-sum and right-sum>cross-sum) 
    return (right-low, right-high, right-sum)
else 
    return (cross-low, cross-high, cross-sum) 

/*辅助算法: 找跨越中点数的最大子数组*/
Find-Max-Crossing-SubArray(A, low, mid, high) 
left-sum = -9999
sum = 0
for (i=mid; i>=low; i--)
    sum = sum+A[i]
    if (sum > left-sum)
        left-sum = sum
        max-left = i
right-sum = -9999
sum = 0
for (i=mid+1; i<=high; i+)
    sum = sum+A[i]
    if (sum > right-sum)
        right-sum = sum
        max-right = i
return (max-left, max-right, (left-sum+right-sum) )

时间复杂度分析: (分治类常用)
(1)写出递归式: T(n) = T(n/2) + T(n/2) + Θ(n) + Θ(1) = 2T(n/2) + Θ(n)
(2)使用主定理: n^(log(b下a上)) = n = f(n) , 所以T(n) = Θ(nlgn)

• 多数问题;
• 矩阵Strassen*

===========作业===========

• majority
• 3-4 助教题目
• 上机题 做最大子数组(分治)
• 递归的主定理的证明, 要搞明白怎么用怎么来的;