Divide and Conquer-week6-8/89

6.Divide and Conquer-11

The divide-and-conquer strategy tries to make the most of this idea:
1.Divide the given problem instance into smaller instances.
2.Solve the smaller instances recursively.
3.Combine the smaller solutions to solve the original instance.
• This works best when the smaller instances can be made to be of equal (or near-equal) size. 最好的情况是实例被平分

11-7

11-8 将实例划分为b个小实例，这些实例将被解决a次，f(n)是划分实例和结合实例所花费的时间

6.1The Master Theorem

11-9

例1：

T(n)=2T(n/2)+n
a=2,b=2,d=1 a= b^d =2^1

T(n)=2T(n/2)+n
T(n) = 2(2T(n/4) + (n/2)) + n
T(n) = 4(2T(n/8) + n/4) + 2(n/2) + n
T(n) = 8(2T(n/16) + n/8) +4(n/4) + 2(n/2) + n
T(n) = 16T(n/16) + 8(n/8) + 4(n/4)+ 2(n/2) + n

11-19

所以T(n)应该是Theta(n logn),共计算了log2(n)次，每一次都比上一次加上n。

例2

T(n) = 4T(n/4) + n
a=4,b=4,d=1 a=b^d =4^1

T(n) = 4T(n/4) + n
T(n) = 16T(n/16) + 4(n/4) + n
T(n) = 64T(n/64) + 16(n/16) + 4(n/4) + n

11-29

例3

T(n) = T(n/2) + n
a=1,b=2,d=1 a<b^d=2

T(n) = T(n/2) + n
T(n) = T(n/4) + n/2 + n
T(n) = T(n/8) + n/4 + n/2 + n

11-36

所以T(n)应该是Theta(n),b不管计算了多少次，所有的相加都不会超过2n。

例4

T(n) = 2T(n/2) + n^2
a=2,b=2,d=2 a<b^d=4

T(n) = 2T(n/2) + n^2
T(n) = 2(2T(n/4) + (n/2)^2) + n^2= 4T(n/4) + 2(n/2)^2 + n^2
T(n) = 8T(n/8) + 4(n/4)2 + 2(n/2)2 + n2

11-46

所以T(n)应该是Theta(n^2 ),b不管计算了多少次，所有的相加都不会超过2(n^2)。

6.2Mergesort

Perhaps the most obvious application of divide-and-conquer:
• To sort an array (or a list), cut it into two halves, sort each half, and merge the two results.

11-61

11-47/62

p、q分别是数组B和数组C的长度，i、j、k分别表示在数组B、C、A中的位置

• 步骤：
  1.遍历B和C的数据，找到两个之中最小的就填入A中
  2.若一个数组的所有数据都已经结束，另一个数组的剩余数据之间填入A的空余位置。
  
  11-69
  
  
  11-88
  
  递归中，MERGESORT的时间复杂度为2C(n/2),MERGE的时间复杂度为n-1，需要做n-1次对比并插入。

Mergesort总结：
1.其最差情况时间复杂度为Theta(n logn)，平均情况时间复杂度为最差情况时间复杂度的75%。
2.Mergesort是stable的
3.Mergesort不是in-place
4.在随机数据情况下，Mergesort的时间大于quicksort但小于heapsort。
5.Mergesort适用于linked lists链表和非常大的数据集合。
6.divide-and-conquer approach

11-92（不考）

6.3Quicksort

It uses the partitioning idea from QuickSelect, picking a pivot element, and partitioning the array around that, so as to obtain this situation:

11-93

• The element A[s] will be in its final position (it is the (s + 1)th smallest element).
• All that then needs to be done is to sort the segment to the left, recursively, as well as the segment to the right.

11-94/106

• Quicksort步骤：
  1.做partitioning，将第一个数看作pivot支点，将小于它的放在它左边，大于它的放在右边
  2.将左右两个部分分别带入Quicksort进行partitioning递归排序
  
  
  
  
  
  
  
  
  
  11-118

• Hoare Partitioning步骤：
  1.将一个数看作pivot支点，将第二个数和最后一个数的索引放入i、j
  2.i向后找到一个大于pivot的数，j向前找到一个小于等于pivot的数，交换，并重复次步骤知道i>j所有元素遍历完成
  3.再一次交换i，j
  4.交换j、pivot

11-/119121

两种优化方法

1.Median-of-Three

11-122 找三个数，将中值放在第一个位置，确保pivot会在中间位置更有可能将数组平分，最大值放在最后能减少一次比较。

11-123

2.Early Cut-Off

11-124 提早结束quicksort，然后转为 insertion sort，因为 insertion sort在面对almost sorted的数组时，反应更快

Quicksort总结
1.divide-and-conquer approach
2.最优情况是pivot为中值，数组被平分，时间复杂度为Theta(n logn),与mergesort最差的时间复杂度相等
3.最差情况的时间复杂度为Theta(n^2),数组是已经排序好的，说为divide-and-conquer实际每次只减1.
4.Quicksort的平均时间复杂度趋近于其最优时间复杂度为Theta(n logn)，有很快的平均时间复杂度。
5.有两种优化方法Median-of-Three和Early Cut-Off，在使用优化方法的时候Quicksort被认为是随机数据的最好排序方法
6.在最里面循环的PARTITION控制了Quicksort的运行速度
7.Quicksort不是stable的，是in-place的

6.4Tree traversal

12-4 链表结构

12-6 二叉树结构

• concepts
  height：从零开始的最大level，有五层hieght则为4
  full binary tree:Each node has 0 or 2 (non-empty) children. 树的空nodes只能在最下面两层
  complete tree: Each level filled left to right. 树的空nodes只能在最下面两层
  external nodes：空nodes，一般个数为n+1

12-10 full binary tree

12-10 complete tree

function HEIGHT(T)
  if T=null then  //basic operation
    return -1
  else 
    return max(HEIGHT(T.left),HEIGHT(T.right))+1

时间复杂度为internal and external做的比较，为n+(n+1)=2n+1

6.4.1 树遍历的四种方法

1. Preorder traversal visits the root, then the left subtree, and finally the right subtree.中 左 右
2. Inorder traversal visits the left subtree, then the root, and finally the right subtree.
   左 中 右
3. Postorder traversal visits the left subtree, the right subtree, and finally the root.左 右 中
4. Level-order traversal visits the nodes, level by level, starting from the root. 分层

例：

12-14

12-48 Preorder traversal -Visit order: 17 33 19 16 38 31 48 11 14

12-94 Inorder traversal--Visit order: 19 33 38 16 31 17 11 48 14

12-133 Postorder Traversal--Visit order: 19 38 31 16 33 11 14 48 17

12-134 Preorder Traversal Using a Stack 这里的T/T.right都是指针

12-161 Level-Order Traversal Using a Queue--Visit order: 17 33 48 19 16 11 14 38

6.5Closest Pair revisited

In Lecture 5 we gave a brute-force algorithm for the closest pair problem:
The brute-force method had complexity Θ(n2). We can use divide-and-conquer to do better, namely Θ(n log n).

• 步骤
  1.将所有的点按照其x值排序并存储在数组 byX，将所有的点按照其y值排序并存储在数组 byY
  2.找到x为中数的点，以line x=m为界限，将小于其的点和大于其的点分别存储在PL和PR中
  3.分别在PL和PR中找到最短的距离dL和dR，选出其中的最短距离命名为d
  4.在 byY中选出m − d ≤ x ≤ m + d的点，将其放入数组S中
  5.找到S中的最短距离(不需要考虑所有点之间的距离，先找到两个y值小于d的点再计算距离可以减少对比)，选取三个最短距离最小值，得出答案

12-173

binary tree二叉树
recurrences递归
closed forms解析解