algorithms-ch2-divide and conque

The divide-and-conquer strategy solves a problem by:

1. Breaking it into subproblems that are themselves smaller instances of the same type of
   problem
2. Recursively solving these subproblems
3. Appropriately combining their answers

2.1 Multiplication

only three multiplications

bc+ad = (a+b)(c+d)−ac−bd

For instance, if x = 101101102 (the subscript 2 means “binary”) then xL = 10112, xR = 01102,
The product of x and y can then be rewritten as

xy = (2^(n/2)xL + xR)(2^(n/2)yL + yR) = 2^n xLyL +2^(n/2) (xLyR + xRyL) + xRyR.

Time complexity analysis:

• additions take linear time,
• The significant operations are the four n/2-bit multiplications, xLyL, xLyR, xRyL, xRyR;
  so: we get the recurrence relation

T(n) = 4T(n/2)+O(n).

three times multiplications(改进版):

T(n) = 3T(n/2)+O(n).

A divide-and-conquer algorithm for integer multiplication (3次乘法)

function multiply(x,y)
Input: Positive integers x and y, in binary
Output: Their product
/
n = max(size of x, size of y)
if n = 1: return xy
/
xL, xR = leftmost ⌈n/2⌉, rightmost ⌊n/2⌋ bits of x
yL, yR = leftmost ⌈n/2⌉, rightmost ⌊n/2⌋ bits of y
P1 =multiply(xL,yL)
P2 =multiply(xR,yR)
P3 =multiply(xL +xR,yL +yR)
return P1 ×2^n +(P3 −P1 −P2)×2^(n/2) +P2

2.2 Master theorem

master theorem

2.3 Mergesort

归并排序：T(n) = 2T(n/2) + O(n) ==> O(nlogn)
二分搜索：T(n) = T(n/2) + O(1) ==> O(logn)

function mergesort(a[1,...n])
Input: An array of numbers a[1 . . . n]
Output: A sorted version of this array
/
if n>1:
  return merge(mergesort[1.... ⌊n/2⌋]),mergesort(a[⌊n/2⌋ + 1 . . . n]))
else
  return a

function merge(x[1 . . . k], y[1 . . . l])
if k = 0: return y[1...l]
if l = 0: return x[1...k]
if x[1] ≤ y[1]:
  return x[1]◦merge(x[2...k],y[1...l])
else:
  return y[1]◦merge(x[1...k],y[2...l])
//◦ denotes concatenation连接操作 . 
//each merge operation takes k+l operations:O(k+l)

all the real work is done in merg-
ing, which doesn’t start until the recursion gets down to singleton arrays

function iterative-mergesort(a[1 . . . n])
Input: elements a1,a2,...,an to be sorted
/
 Q = [ ] (empty queue)
for i=1 to n:
  inject(Q, [ai ])
//initialize the queue, put all elements in this queue

while |Q| > 1:
  inject(Q, merge(eject(Q), eject(Q)))
//merge 前两个从queue中取出的单元素，再把merge结果插入queue后面，
//注意：queue不是一个存i个元素的数组，在第一次while之后queue中已经存在Q1[ai,aj]这样的东西了，所以最后得到一个完整的Q时，Q = 1，退出循环

return eject(Q)
//完成sort, 按顺序eject queue中元素

排序的下限：涉及两两比较的方法来对一组数进行排序的最优复杂度是O(nlogn)，所以归并排序是最优排序。
Here is the argument: Consider any such tree that sorts an array of n elements. Each of its leaves is labeled by a permutation of {1, 2, . . . , n}. In fact, every permutation must appear as the label of a leaf. The reason is simple: if a particular permutation is missing, when we feed the algorithm an input ordered according to this same permutation, the algorithm's correctness will be uninsured. And since there are n! permutations of n elements, it follows that the tree has at least n! leaves.
We are almost done: This is a binary tree, and we argued that it has at least n! leaves.
Recall now that a binary tree of depth d has at most 2^d leaves (proof: an easy induction on d). So, the depth of our tree—and the complexity of our algorithm—must be at least log(n!).

depth d, last level 2^d leaves;
last level n!, depth log(n!)==complexity: log(n!)=nlogn

大概思路就是：

1. 每个最下面的leaf 表示这n个元素的一种大小排列可能
2. 共会有n！种排列可能，所以最下面一级有n！个leaves
3. 从depth= d ==> last level at most 2^d leaves 推出last level n! ==>depth log(n!)
4. 算法复杂度=log(n!)=nlogn

注意：存在线性排序（O(n)），此法不涉及两两比较。例：对1,2,3,4,5,8,9,19,20排序，设一个bool型数组a[1..20],初值全为false，顺序扫一遍输入，扫到n，则把a[n]设为true，然后扫一遍a，把值为true的输出，即已排好序。但不适合对大数字排序。空间换时间

2.4 medians

find the medians:

1. sort the elements, nlogn
2. SELECTION
   Input: A list of numbers S; an integer k
   Output: The kth smallest element of S

For any number v, imagine splitting list S into three categories

• elements smaller than v, SL,
• those equal to v (there might be duplicates), Sv
• and those greater than v. SR

SL,Sv, and SR can be computed from S in linear time

• if we choose v , such that |SL|,|SR| ≈ 1|S|.
  running time : T (n) = T (n/2) + O(n),
• if we choose v = max/min number of s.
  running time : T(n)=Θ(n2)
• if we choose v = median
  running time : T(n)=O(n),
• we will call v good if it lies withinthe 25th to 75th percentile of the array that it is chosen from, We like these choices of vbecause they ensure that the sublists SL and SR have size at most three-fourths that of S

2.5matrix multiplication

The product of two n×n matrices X and Y is a third n×n matrix Z=XY, with (i,j)th entry

(i,j)th entry

T(n) = 8T(n/2) + O(n2).

可以分解成7个n/2规模的子矩阵乘法，

T(n) = 7T(n/2) + O(n^2), 解得O(n^2.81)

exercise
Introduction to Algorithms, Third Edition
(CLRS)
4.1-5
Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of A[1...j] , extend the answer to find a maximum subarray ending at index j+1 by using the following observation: a maximum subarray of A[1...j+1] is either a maximum subarray of A[1...j] or a subarray A[i...j+1] , for some 1<=i<= j+1 Determine a maximum subarray of the form A[i...j+1] in constant time based on knowing a maximum subarray ending at index j .
//题目要求看起来有点像动态规划

find-maximum-subarray(A, low, high)

array.left = 0
array.right = 0
sum = A[low]
tempSum = 0
for i = low to high
  tempSum = Max(A[i],tempSum+A[i])
  if tempSum>sum
    sum = tempSum
    right = i
  if tempSum == A[i]
    left = i
return (left,right,sum)