概述

本篇供日后复习，跳跃性很大，随性更新。

参考书目：《算法设计与分析》黄宇机械工业出版社

第2章从算法的角度重新审视数学的概念

2.1.3 阶乘n!

根据Stirling公式，可以将n!转化为更易于处理的闭形式，对n>=1，有：

$$ \sqrt{2\pi n}(\frac{n}{e})^n < n! < \sqrt{2\pi n}(\frac{n}{e})^n(1+\frac{1}{11n}) $$

Stirling公式也可以写成：

$$ n! = \sqrt{2\pi n}(\frac{n}{e})^n e^{\varepsilon(n)},其中\frac{1}{12n+1} \leq \varepsilon(n) \leq \frac{1}{12n} $$

写成近似形式：

$$ n! = \sqrt{2\pi n}(\frac{n}{e})^n(1+\Theta(\frac{1}{n})) $$

由于 $\Theta(\frac{1}{n})$ 是无穷小量，$\lim\limits_{n \to \infty} \frac{1}{n}=0$ ，忽略。所以得到进一步的近似式：

$$ n! \approx \sqrt{2\pi n}(\frac{n}{e})^n $$

2.1.4 常见级数求和 $\sum\limits_{i=1}^{n}f(i)$

多项式级数(polynomial series)
$ \sum\limits_{i=1}^{n}i = \dfrac{n(n+1)}{2} $
.
$ \sum\limits_{i=1}^{n}i^2 = \dfrac{1}{3}n(n+\dfrac{1}{2})(n+1) $
.
$ \sum\limits_{i=1}^{n}i^k = \Theta(\dfrac{1}{k+1}n^{k+1}) $
.
几何级数(geometric series)
$ \sum\limits_{i=0}^{k}ar^i = a(\dfrac{r^{k+1}-1}{r-1}) $

测试用
$\begin{eqnarray}f(x,y)
&=&2xy+(x-y)^2\
&=&x^2+y^2
\end{eqnarray}$

第0章概论

杂记

Q1: 在数组中找最大元素和最小元素

A1: 最优：n为偶数时，将数组切分为($a_0$,$a_1$)($a_2$,$a_3$)…($a_{n-2}$, $a_{n-1}$)，组内比较后分出胜者组和败者组，胜者组遍历一遍得到最大元素，败者组遍历一遍得到最小元素。n为奇数时先抛开最后一个元素，最后额外比较一下。

Q2: 比较3匹马的预测性

A2: 将马的过去两百场比赛进行huffman编码，所用字符最少的马预测性越强，原理是信息熵。

Q3: 停机问题

A3: 不可判定，假设有程序terminate(p:program, x:input)能判断对于程序p，给一个输入x，p是否会终止（即判定p(x)是否终止），那么定义程序paradox(z:file)

1 2	paradox(z:file): 1: if(terminate(z, z)) goto 1;

paradox(z)的执行结果为
$$
\left{
\begin{array}{aligned}
z(z)不终止 && {paradox(z)终止}\
z(z)终止 && {paradox(z)不终止}\
\end{array} \right.
$$

此时，paradox(paradox)便成为矛盾体
$$
\left{
\begin{array}{aligned}
paradox(paradox)不终止 && {paradox(paradox)终止}\
paradox(paradox)终止 && paradox(paradox)不终止
\end{array} \right.
$$

课程任务：

书面作业15%（8次，准备2个作业本）
编程15%（6-8次，每次2-4题，时间2-3周）
期中20%
期末50%

第1章概论

《proof without words》中的有趣证明？

double counting 思想用于证明

平均复杂度

$ \sum\limits_{i=1}^{n}Pr(i)I(i) $

算法的最优性

如果一个算法的最坏情况等于问题的下界，那么这个算法是最优的。

第2讲渐进时间复杂度

$ log_{n}, n^\alpha, c^n, n!, n^n $

$$
\lim\limits_{n\to \infty}\frac{f(n)}{g(n)}=c,
\left{
\begin{array}{aligned}
c=0 && f=o(g)\
0 \leq c < \infty && f=O(g)\
0 < c < \infty && f=\Theta(g)\
0 < c \leq \infty && f=\Omega(g)\
c = \infty && f=\omega(g)
\end{array} \right.
$$

不是所有俩函数之间都有上述五种关系，比如$ f(n)=n, g(n)=n^{1+sin n}$，极限不存在。

决策树

决策树的高度p是问题的lower bound，基于比较的决策树节点数为n，有$ n \leq 2^{p-1} $，所以$ p >= lgn $，所以查找问题的lower bound为$lgn$，二分查找是最优算法。

无关思考题：圆的内接八边形，边长4个2，4个3，求八边形面积。
放到正方形里去，减去四个角的等腰直角三角形

$$
f(n) =
\begin{cases}
n/2, & \text{if $n$ is even}\
3n+1, & \text{if $n$ is odd}
\end{cases}
$$

第3讲递归

时间复杂度计算

齐次线性

$ a_n = r_1a_{n-1} + r_2a_{n-2} + … + r_ma_{n-k} $

特例
$ 形如T(n)=r_1T(n-1)+r_2T(n-2),有特征方程x^2 = r_1x + r_2x $
$ 则T(n) = ux_1^n + vx_2^n. $

证明：
$ B.C: T(1), T(2) $

$ I.H: 1 \leq m < n, T(m) = ux_1^m + vx_2^m $

$\begin{eqnarray}T(n)
&=& ux_1^n+vx_2^n\
&=& ux_1^{n-2}x_1^2+vx_2^{n-2}x_2^2\
&=& ux_1^{n-2}(r_1x_1+r_2)+vx_2^{n-2}(r_1x_2+r_2)\
&=& r_1(ux_1^{n-1}+vx_1^{n-2})+r_2(ux_1^{n-2}+vx2^{n-2})\
&=& r_1T(n-1)+r_2T(n-2)
\end{eqnarray}$

代价 = 递归代价 + 非递归代价

$ T(n) = bT(\frac{n}{c})+f(n) $

after $k$ th expansion

$ T(n) = b^kT(\frac{n}{c^k})+\sum\limits_{i=1}^{k}f(\frac{n}{c^{i-1}}) $

意味着递归树高度$\log_c n$

$$
\sum\limits_{i=0}^{n-1}=
\begin{cases}
n/2, \text{xxx} \
ss
\end{cases}
$$

最大子序列之和

暴力枚举
算法：取所有sequence[i, j]，比较。
时间复杂度：$O(n^3)$
减少重复计算
二分，最长要么在左，要么在右，要么有左有右

假设A[0, n]中最大和为M[0, n]，那么A[0, n+1]中最大和为$\max{M[0,n], \sum\limits_{i=0}^{n}A_i, \sum\limits_{i=1}^{n}A_i, …,\sum\limits_{i=n-1}^{n}, A_n}$

当前和一直加，保持增长，如果小于0，就丢弃前面的（即丢弃当前和）

ThisSum = MaxSum = 0;
for(j = 0; j < N; j++) {
    ThisSum += A[j];
    if(ThisSum > MaxSum) {
        MaxSum = ThisSum;
    }
    else if(ThisSum < 0) {
        ThisSum = 0;
    }
    return MaxSum;
}

一个盘子可以被n个直线最多分为多少块

L(0) = 1
L(n) = L(n-1) + n

合法字符串

字符串只有abc三种字符，aa不允许出现，长度为n的合法字符串有多少个

f(1) = 3
f(2) = 8
str(n) : ab+str(n-2)
: ac+str(n-2)
: b+str(n-1)
: c+str(n-1)
f(n) = 2f(n-1)+2f(n-2)

矩阵乘法

strassen’s alogorithm runs in $O(n^{2.81})$

f(n) = 7f(n/2) + $\Theta(n^2)$

第4讲 quick sort

易合难分

partition的方法不同
最坏复杂度分析
平均复杂度分析

第5讲 merge sort

易分难合

第6讲 heap sort

common version

accelerated heap sort

第7讲选择

找最大最小元素

找第2大元素

找第k大/小元素

找中位数

算法1：

寻找 pivot，将数组分两半，在基数比较大的一半里找第 n/2 - |S小| - 1 小的元素
最坏情况：
类似快排，pivot选不好

6次比较找出5个元素中的中位数：

算法2：

第8讲 adversary & BST

判断5个元素中是否有3个连续的1

3次之内不够
对手策略：定义 x: 1 1 1 1 1, y: 0 0 0 0 0，我想看第i位的值，就先去 x 里看，如果把 xi 变成0还能保证有3个连续1，那么把 xi 变成0，否则把 yi 变成1.

4次：

判断图的连通性

必须看$\frac{n(n-1)}{2}$次，否则
对手策略：

性质的单调性：图有这个性质，它的子图也有这个性质

图可平面化：图在平面上可以画出边不相交，条件是不含 K3,3 和 K5 这两个子图

二分搜索

例如求$\sqrt{N}$
当 N 很大时，等于是找 x，使得 $ x^2 \leq N, (x+1)^2 > N $

AVL tree

RB tree

搜索的 tutorial

扔鸡蛋问题

Q: n 层楼，从某层楼扔下去鸡蛋会碎，求这个楼层

如果只有1个鸡蛋，easy
如果有无穷多个鸡蛋，二分法
如果有2个鸡蛋
A1: 每隔$\sqrt(n)$层扔1个鸡蛋，尝试次数为$\sqrt(n) ~ 2\sqrt(n)$
A2: 第1次，从x层扔（碎了，最坏比x次，没碎继续），第2次从2x-1层扔（碎了，比1+x-1次，没碎继续），。。。共 (x+1)x/2 层，令它 >=n 就求得了 x

找名人

Q: n 个人，名人定义：被其他所有人认识，但不认识其他任何人，操作是拿A和B来，问A是否认识B，B是否认识A
O(n)算法：每次比较可以淘汰1个人

赛马问题

Q: 共25匹马，每次可以选5匹马进行比赛，并得到次序（无法计时），问至少要多少次比赛才能确定跑的最快、第二快、第三块的马

最快的：比赛6次即可
第二快：出现在第1快的那一组的第2名（1匹），以及所有组第一快里的那5匹里输给第1快的第2名（1匹）（只输给最大元素的元素是候选人）。
第三快：候选人，第1组第3快，第2组第2快，第3组第一快

共7次找出前三快的马

2018 mid-term

Q: 有sort5算法，一次排序5个元素，求n个元素的最大值和第二大

最大值：一次sort5丢弃4个元素，所以最多比较$\frac{n-1}{4}$取上整

第二大：采用5叉胜者树，即可得出 max，和仅仅输给 max 的元素

带权中位数

Q: 所有权之和为1，带权中位数$ x_k: \sum_{x_i < x_k}{w_i} < 1/2 且 \sum_{x_i > x_k}{w_i} \leq 1/2 $
A: 找普通中位数，判断行不行，小不行就将小于它的权和加到它头上，然后递归后半部，大不行就同理

最小未出现自然数

n个大小不同的自然数E[1]~E[n]，找出不在这个自然数序列中出现的最小自然数

若已排序，二分查找，若E[n/2]>n/2，在前一半，若等于，在后一半，不可能小于..
若未排序，
法1：开n位数组，遍历，出现置1，然后第一个0元素下标就是
法2：找中位数x，按x和n/2大小丢掉一半元素

前k大的数们

排序，取后k个，nlogn
建堆+取出k个元素，n+klogn
先找第k大元素，n，再遍历找出比第k大都大的元素，n，然后排序，klogk，合计 n+klogk

两个已排序数组中的第k小元素 LeetCode-

merge到第k个就行，$\Theta(k)$
找两数组中位数A[m/2], B[n/2]
若 m/2+n/2 < k，若A[m/2] > B[n/2]，说明比B[n/2]小的元素数量[n/2, m/2+n/2]，所以确定比B小的B的前半部分可以丢了
若 < ，丢A的前半部分

5个元素6次比较找中位数讲过了，7次比较排序

ppt

k个已排序树组 merge 策略

两两merge

哈希表

简单一致哈希假设

并查集

均摊时间代价

accounting cost

这个真不会，[UST]

一般是对一系列操作进行分析才使用均摊分析，分析出一次操作的代价，而且这些操作是由规律的

accounting cost 之和必须大于0，这样计算出的 amortized cost 是 actual cost 的一个上界

二-计数器 ppt上的

发现：一开始每一位都是0，
每一位想要从1变为0，首先得从0变为1，于是把0->1的accost 为1，1->0的ac cost为-1，这样 ac cost 始终大于0

聚合法

比如作业那个三-计数器，个位每次变，十位每3次变，百位每9次变。。所以操作n次increment，变了n+n/3+n/3^2+…. < 2n

栈的pop，multipop，可见每次操作

势能法？potential method

统一 hash

解决类似快排 partition 没选好的问题，快排随机选 pivot

期中考试讲解

根节点到最深节点的路径长度就是基于比较的排序的最坏情况
(2) 逆序对的情况只能是 (i,i+1) (j, j+1) 或 (i, i+2) (i, i+1) 或 (i, i+2) (i+1,i+2)
(2) 看 tutorial，找中位数，如果满足直接返回，不满足就把某一半边的权重加到中位数上，然后继续递归另一半边
其实链表就可以了？删除时的代价n在插入时每次 accounting cost 预付掉，然后就是常数级别的了

概述

第2章 从算法的角度重新审视数学的概念