Algorithms: Design and Analysis, Part 1

Reading time ~15 minutes

重学Coursera 上的Algorithms: Design and Analysis, Part 1 以期巩固Algorithms 相关知识。如后为课程笔记。

Week 1

推介了一些算法书籍

然后重点是介绍一些基本概念:

  • $T(n) = O(f(n))$ if and only if there exist constants $c,n_0$ such that $T(n) \le c* f(n), \forall n \ge n_0$
  • $T(n) = o(f(n))$ if and only if for all $c>0$, there exist constant $n_0$ such that $T(n) \le c* f(n), \forall n \ge n_0$
  • $T(n) = \Omega(f(n))$ if and only if there exist constants $c,n_0$ such that $T(n) \ge c* f(n), \forall n \ge n_0$
  • $T(n) = \theta(f(n))$ if and only if $T(n) = O(f(n))$ and $T(n) = \Omega(f(n))$
    • that is, there exist constants $c_1, c_2, n_0$ such that $ c_1 * f(n) \le T(n) \le c_2 * f(n), \forall n \ge n_0$

然后是Divide&Conquer 的例子,比如MergeSort 以及大数相乘等的解决方案。

大整数相乘 对求$x*y$ 的值可以分解为

`x=10^(n/2)a+b, y=10^(n/2)c+d`

则:`x*y=(10^n * ac + 10^(n/2) * (ad+bc) + bd)`,此式需要4次乘法,那么再简化一下得

`x*y=(10^n * ac + 10^(n/2) * ((a+b) * (c+d) -ac - bd) + bd)`

那么就可以只有三次乘法。而且这完全也可以实现大数相成结果的计算。

矩阵相乘 这个跟上面类似,可以把一个矩阵四分,然后相乘;接着也可以把乘法次数减少,需要提前构造子矩阵的加减然后再乘:

`X * Y = ((A, B), (C, D)) * ((E, F), (G, H)) = ((AE+BG, AF+BH), (CE+DG, CF+DH))`

Counting Inversions 假设有长数组A,对于所有的索引i<j 如果 A[i]>A[j] 则构成一个inversion。找数组A中的inversions count 跟mergeSort 类似($n log n$ 的复杂度)

  1. 假设方法是invCount()
  2. divide A 成两个小数组a, b
  3. 最后invCount(A) = invCount(a)+invCount(b)+invSplitCount(a,b),其中invSplitCount 代表i 再a 中,j 在b 中构成的inversions 数量。

我们发现,当a, b有序时,invSplitCount 就非常好数(即A[i]>A[j] 时,a 中比A[i] 大的都能跟A[j]构成inversion )

所以以上步骤再做优化即为:

  • invCount 需要sort 数组a,b
  • invSplitCount 里额外进行mergeSort

具体可参见Julia 算法代码

Closest Pair 找数组中最相近的两个数(排序n log n,找相近 log n)。找平面中最接近的两个点等(D&C)。

Make copies of points sorted by x-coordinate (Px) and by y-coordinate (Py)[O(nlog(n)) Time]

  1. Let Q=le] half of P, R=right half of P. Form Qx, Qy, Rx, Ry [takes O(n) time]
  2. (p1,q1)=ClosestPair(Qx,Qy) 一部分最近点
  3. (p2,q2)=ClosestPair(Rx,Ry) 另一部分得到的最近点
  4. let $\delta = min ({d(p1,q1), d(p2,q2)})$
  5. (p3,q3)=$ClosestSplitPair(Px,Py, \delta)$ 如果最近点一个落在Q 内,一个落在R 内,通过均值的$\delta $ 范围内 $[\bar x-\delta, \bar x + \delta]$ 找最近点
  6. Return best of(p1,q1),(p2,q2),(p3,q3)

Week 2

Master Method

总结如MergeSort 形式的递归问题的复杂度一般形式:

` T(n) = a T(n/b) + O(n^d) `

其中 a 为子问题个数,b 为子问题相形与原问题缩小的比例,d 为combine 步骤的复杂度。 考虑像MergeSort 这种算法,在第j 层时,有$a^j$ 个子问题,每个子问题大小为$n_j = \frac {n} {b^j}$ ,则单个子问题combine 复杂度为$n_j^d$ ,则单层总的算法复杂度就为:

` T(n_j) <= a^j * c * (n/(b^j))^d = c * n^d (a/b^d)^j `

而总的层数为$log_b n$。则:

` T(n) <= c * n^d sum_{j=0}^{log_b^n}(a/b^d)^j `

那这种问题的复杂度,就可以根据新的一层复杂度是否收敛($\frac {a}{b^d}$ 与1 的大小关系,确定最复杂的是首层、还是最后一层、还是每层都一样),而归纳一般形式为:

\[T(n)= \begin{cases} O(n^d log n), & \text{if $a = b^d$}, \cr O(n^d), & \text{if $a < b^d$}, \cr O(a^{log_b^n}), & \text{if $a > b^d$} \cr \end{cases}\]

QuickSort

基本思想:找到pivot,然后把小的放左面,大的放右面,从而迭代求解。

如果使用O(n) 的额外空间,可以非常方便的,在迭代过程中小的从左面开始存,大的从右边开始存,然后pivot 肯定在中间。而如果不使用额外的空间。设数组为A,则可用如后的具体步骤:

  1. 把第一个数作为pivot
  2. 从第二个数往后扫描,设j表示扫描到的新元素的索引,设A[i-1]<pivot,而A[i]>pivot
  3. 若A[j]<pivot,则把A[i]、A[j] 两数交换
  4. 继续向后扫描,重复2-4,指导结束。
  5. 交换pivot 和 A[i-1] 两个数,再排左右两个子串

具体代码实现可见Julia 代码

快排,依赖选择的Pivot 的质量。所以通常随机选择pivot (然后再切换到第一个数,重复上面的步骤)效果会比一直选择首个、末尾数好。而选择首、尾、中间三数的median 会更好。

Probability

  • 设$\Omega$ 为可能的结果全集(Sample Space)
  • 某个事件S,就可以是$\Omega$ 的子集
  • Randome Variable $X$:就是将$\Omega $映射到实数空间的函数
  • 期望`E[X] = sum_(i in Omega) X(i) * p(i)`
  • Linearity of Expectation:

    Let $X_1,…,X_n$ be random variables defined on $\Omega$ Then: `E[sum_{j=1}^n X_j] = sum_{j=1}^n E[X_j]`

  • Conditional Probability: `P[X|Y] = (P[X nn Y]) / (P[Y])`
  • if A,B are independent, then $E[AB] = E[A]*E[B]$

Week 3

Randomised Selection

假设一个算法,输入一个数组A,找出其第k 大的数。我们可以把该数组MergeSort 然后取第n 大就行。但是这$n log n$ 的算法不是最好。

我们可以用QuickSort 里的partition 思想。每次partition 之后,知道pivot 的位置后,也就知道该数在pivot 的左边还是右边,然后依次迭代下去。

当然pivot 的选择,依然是用median 比较好,不然最差的情况是$O(n^2)$ 的复杂度。假设随机选择,能达到median 的效果,如此便是

`T(n) = T(n/2) + O(n)`

的问题,复杂度也就是$O(n)$

Deterministic Selection

上面讲到的Media 的选择,可以使用 median of medians 算法选择pivot

  • logically break A into n/5 groups of size 5 each
  • sort each group (e.g., using Merge Sort)
  • copy n/5 medians (i.e., middle element of each sorted group) into new array C
  • recursively compute median of C (!)
  • return this as pivot

如此,pivot 选择的复杂度是`T(n)<= T(n/5) + O(n)`,而因为上面的MoM 算法选择median of medians后,那么C 的小于或大于median 的数至少有`3*n/5 * 1/2` 则新的算法的复杂度:

`T(n) <= T(n/5) + T((7n)/10) + O(n)`

Sorting Lower Bound

假设$n!$ 个数,我们需要k 次比较才能把他们排好,那么最多执行$2^k$ 次计算(比如MergeSort 形式的二叉树)。则

By the Pigeonhole Principle : if $2^k < n!$, execute identically on two distinct inputs => must get one of them incorrect. So, `2^k >= n! >= (n/2)^(n/2)`

所以 `k>= Omega(n log n)`

Graphs

Cuts of Graphs

a cut of a graph (V, E) is a partition of V into two non-empty sets A and B.

the crossing edges of a cut(A, B) are those with:

  • the one endpoint in each of (A, B) [undirected]
  • tail in A, head in B [directed]

min cut Compute a cut with fewest number of crossing edges.

Adjacency Matrix 使用矩阵A,用A[i][j] 表示`i-j` 这一条边:

  • 无向图用0/1 表示有无此边,或设置边的权重值
  • 有向图使用+1/-1 表示`i->j` 或 `j->i`

Random Contraction

While there are more than 2 vertices:

  • pick a remaining edge (u,v) uniformly at random
  • merge (or “contract” ) u and v into a single vertex
  • remove self-loops return cut represented by final 2 vertices.

设图G 有m 个边,n 个点,而MinCut 有k 个crossing edges(设为集合F )。 而所在点的度的和`sum_v degree(v) = 2m >=kn `,那么F 被Radom contraction 选中的概率为`k/m <= 2/n `,

所以每次选中非F 中的点的概率为`1-2/n = (n-2)/n`, 则RC 得到MinCut 的概率为 ` p >= prod_(k=3)^n (k-2)/k = 2/(n*(n-1))`

Week 4&5

介绍图的BFS 和 DFS 搜索。BFS再深入介绍的Dijkstra Algorithm 求最短路径,DFS 这是求强联通图。

强联通图的计算步骤:

  • 有图G后, 计算每条边取反向得到的G_rev。
  • 在G_rev 上调用DFS-Loop 算法,然后每个节点的结束时间存入ft。
  • 在G 上,按照ft 中最晚结束的节点最先搜索的原则,调用DFS-Loop 算法。
  • SCCs 就是有相同leader 的所有节点。

DFS-Loop 算法:

for i = n:-1:1
    l = i
    DFS(Graph,i, l) 
    # 然后从i DFS直到结束,这词DFS 节点的leader 都为l。
end

强联通图的算法可参见SCC.jl 实现。

Dijkstra’s Algorithm,BFS 的代表。假设需要计算s 到任意节点的最短路径。代码可参照Dijkstra.scala,算法思想如后:

  1. 用X 表示遍历过的节点,B、A分别记录每个节点的最短路径及其长度。初始化$X=[s], A[s]=0, B=[]$
  2. 对于如后集合`{(v,w)|v in X, w !in X}` 的每个节点 $(v,w)$ 使得 `{(v^**, w^**)} = arg min _ (v,w) A[w]= arg min _ (v,w) A[v]+l_(vw)`
  3. 更新 `A[w^**] = A[v^**] + l_(v^** w^**)` `B[w^**] = B[v^**] + u_(v^** w^**)`
  4. 所有节点都被遍历后结束

Mathjax was not loaded successfully

Original post: http://blog.josephjctang.com/2015-10/algorithms-design-and-analysis/

重操堆文这旧业之时间日志分析

写作的习惯,已经断了许久了。上一篇已经是去年的文章了,也是做的[时间日志分析]({% post_url 2019-02-23-time-log-analysis %}) 。 正好做时间总结,也把写作捡起来吧。# 低效时间分析用 [RescueTime](https://www.rescueti...… Continue reading

个人近期时间日志分析

Published on February 23, 2019

问问题的妙用

Published on May 27, 2018