part1

m mod n = m - [m/n] * n

平均时间复杂度

Pr(I):I的出现概率如何获取？根据经验、简单假设、特殊场景

t(I):耗时

证明最优性

算法A是最优的 （upper = lower）

渐进时间复杂度

仅表示n足够大之后的关系，不表示任何时刻的大小。
$$
lgn ∈ o(n^a) 对任意a>0
$$

$$
n^k ∈ o(c^n) 对任意 c>1
$$

$$
n!>2^n
$$

查找问题

顺序查找：A=n/2+O(1)
二分查找：A=lg(n+1)-q 用决策树证明最坏情况比较次数是lg(n+1):从根节点到叶结点的最长路径

求解时间复杂度

用关键操作作为次数。

替换法解递归

特征方程法

不太常用。

guess and proof

两侧都证明一下最准。

递推树

常用公式

重点题

1、有效字符串数量 abc 不能有aa 很巧妙的分治法！

2、guess and proof化成好证明的形式

3、多用归纳法多找规律

part2

插入排序

最差和平均时间复杂度都是O(n^2)

快速排序

法一：不断找HighVac和LowVac，好理解但是算法比较难写

通过guess and proof证明两个方向，可得时间复杂度为O(nlgn)，空间复杂度是O(n)

法二：partition更简明的实现

J：指向没有排序的第一个元素

i：指向<=x的最后一个元素

i+1后指向A[j] 已知A[j]<=x 所以交换相当于**<=x的域**增大了

然后再把j++，继续比较。ij之间的是>=x的元素

归并排序

把两个已排序的数组合并。一个序列的元素远小于另一个序列，这样的merge如何处理？Using binary search.

越平衡epl越小，所以从两个方向证明了算法的复杂度。

还可以不用递归，用队列迭代实现合并排序：

堆排序

1.层 = 1 + 结点与root之间边的个数

2.深度 = 层 – 1 = 结点与root之间边的个数

3.结点高度：与叶结点leaf的最长距离

4.树高度：root的height

fixheap：θ(h)=θ(logn)

fixHeap：把最后一个元素设为root 然后自顶向下最差情况：2h次比较

堆的构建θ(n)

递归：左子树是堆，右子树是堆，把K插到root，然后用fixheap修复即可

W(n)=W(n-r-1)+W(r)+2lg(n) 得到线性时间θ(n)

堆的排序θ(nlogn)

不断取root，然后用fixheap修复

利用堆数组下标的规律堆排序的复杂度是θ(nlogn)

利用分治思想（二分）可提高fixHeap效率，从2nlogn变成nlogn

堆可实现优先级队列。

其他排序：Shell sort/Radix sort O(kn)/Bucket sort在桶内排好序

用递归树分析，平均情况更接近best case而不是worst case

重点题

1、

重点是用折半查找找最近的点

2、

利用quciksort中的partition操作（可以有效划分颜色区域），设定 red < white < blue

1）选择white作为pivot，那么 <= white 的为 red和white， >white 的为blue

2）选择red或者white作为pivot，对 “<= white 的为 red和white” 部分进行排序

复杂度<=2(n-2) = O(n), where n is the number of all elements in the given array

3、逆序对个数用归并排序

4、

找x=a+b：对B排序：nlgn，排序后遍历a，通过二分查找看b——>O(nlgn)

5、

解答：难点在于想到b+S和最接近！！！

6、匹配螺丝螺帽问题，注意只能把螺丝和螺帽比较！

Partition并不是排序，只是把小的和大的放两边，所以要继续递归

7、

寻找第k大的数最重要的是在前k层可以忽略后面的n-k层

8、

从右上角找！x=c找到 x<c 不在最后一列 x>c不在第一行时间复杂度O(m+n)空间复杂度O(1)(没用其他空间)

9、

找Maxima：相当于从右下角开始找小红点！i从大到小很重要

part3

找最大值和最小值

若只找最大值：用对手论证证明必须要n-1次比较，产生n-1个loser。

对手论证分析：max/min只有1个标签，其他2个至少2n-2个标签：根据下图，至少比较n/2+n-2次

找第二大元素

只输给过max，备选元素最多有[lgn]个元素

而可用对手论证迫使max和[lgn]个元素比较过：每次比较后新权重不超过旧权重的2倍

找中位数

Select-Elinear期望线性时间

利用中位数在partition后数量多的一侧。

平均是O(n)，最差是O(n^2)

Select-Wlinear最坏情况线性时间

最差也是θ(n)

任何一个选择算法，必须知道每一个元素和中位数的相对大小关系

找中位数的Lower Bound：(n-1)/2+(n-1)

对手论证

1、5位数有没有111 4次够3次不够（维护11111和00000）

2、判断是否连通：每条边都看否则两种情况均成立

重点题

1、O(n)寻找名人：每次随机找两个人，淘汰一个人

2、

最快的马：至少赛6场

第二快的马：直接输给过A1的马，两个候选：A2和B1

第三快的马：直接“输过”最快或第二快的马，共有3个候选：A3、B2、C1

（2）(3)综合，再比一场比赛，共7场。

3、

1）调用一次SORT5淘汰4个元素，所以使用[(n-1)/4]次

2）直接输给过max的数量是[log5n]（类似于最大元素直接的比较次数为[log2n]）

4、

5、带权中位数

O(nlgn)：先排序然后遍历看weighted median

O(n)：

注意partition可算wL和wG

6、

若已排序：暴力，二分查找（M>n/2：未出现数在前一半；M=n/2：未出现数在后一半）

若未排序：新开一个长为n的flag数组，进行两次遍历；也可以用找中位数的线性算法（M>n/2：未出现数在前一半；M=n/2：未出现数在后一半）

7、3种复杂度

8、

法一：找中位数

若确定有重元素：必然是中位数
不确定：用中位数扫描数组，若数量大于n/2，则有，反之则没有

法二：根据重元素>n/2，其他元素<n/2，遇见不同数字则减1 最终重元素一定次数>=1

part4

二分查找

二叉搜索树

（1）是二叉树（2）右边比根节点大，左边比根节点小

node group 是任意连通的内部节点群

如果S的父节点在这个节点群中，但是S中没有任何节点在这个结点群中，那么S是一个节点群的principal subtree（概念对旋转有用）

红黑树

T是RB TREE：

1、二叉树

2、所有外部结点(叶子结点)是黑色

3、根节点是黑色

4、没有一个红色结点有红色孩子

5、所有叶结点的黑色高度一样：到根节点路径上黑色结点的数量一样（不包括根节点）

T是ARB TREE

1、根节点是红色

2、其他和RB TREE一样

（还有循环定义）

黑色高度为h 内部节点个数为n

n>=2^h-1 至少有这么多结点说明树的黑色高度有上界2lg(n+1)

只要操作得当，增删元素的复杂度都是O(logn)

哈希O(1+α)

闭地址/开散列

用链表结构。增删：O(1) 查询：O(1+α)

开地址/闭散列

查找代价和插入代价均为：1/(1-α) 查找成功的平均代价：

并查集

n个元素，m个操作（union和find）：union操作的复杂度是O(1)find操作的复杂度是O(n) 总复杂度是O(mn)

加权并wUnion+普通查

易证使用wUnion后，k个结点的树高度不超过[logk]。

改进的地方在于find最差不是O(n)，而是O([lgn]+1)。总时间复杂度是O(n+mlogn)

加权并+路径压缩查cFind

*O((n+m)lg*(n))*：让cFind代价变小了

数组扩容的均摊分析：

均摊分析

记账法

1、Multi-pop栈

重点题

1、

找轴值：当ary[mid] > ary[l]时，可以知道轴值一定位于右半边，到底是[mid, r]还是[mid + 1, r]呢，由假定条件ary[mid] > ary[l]可以知道ary[mid]肯定不是最小的元素所以可以区间是[mid + 1, r]。否则，即ary[mid] < ary[l]，可以知道轴值位于左半边，到底是[l, mid]还是[l, mid - 1]呢？我们从这时的假定条件不能继续缩小范围，所以轴值的范围就是[l, mid]。

2、

注意间隔查找的方法。

3、

比较mid index和k的关系

1、a的mid+b的mid比k小：如果a的mid比b的mid大，舍弃b的前一半（太小了）；否则舍弃a的前一半

2、比k大：如果a的mid比b的mid大，舍弃a的后一半（太大了）；否则舍弃b的后一半

4、

查找成功：针对这里的7个数。

查找不成功：对于hash到0的数：一直到6才知道不在里面（看hash到0-9的数）

5、

6、

part5

有向图DFS

O(n+m)

TE：u的邻居v是白色，没有访问过
BE：u的邻居v被访问，且v是u是祖先
DE：u的邻居v被访问，且v是u的后继
CE：u的邻居v被访问，但没有祖先后继关系

活动区间：就是灰色的时间

vw是CE（不重合，没有祖先子孙关系），active(w)先于active(v)
vw是DE（w是v的后继），存在x，active(w)包含于active(x)包含于active(v)
vw是TE，active(w)包含于active(v), 并且不存在x（直接父子关系）
vw是BE，active(v)包含于active(w)（直接父子关系）

白色路径定理

v是w的祖先 iff v刚被发现时，存在一条v到w的全部由白色结点组成的路径

拓扑排序

对于任何边vw，都有（v的拓扑序号）<（w的拓扑序号）

逆拓扑排序（如图代码）：对于边vw：（v的拓扑序号）>（w的拓扑序号）

必须是DAG（有向无环图），否则有循环依赖造成“死锁”。

没有BE！所以对于边vw，一直有finishTime(v)>finishTime(w)

关键路径

假设任务是有持续时间的（AOV网络，AOE网络）

1。est最早开始时间：v没有依赖，est=0；v有依赖，est=依赖的eft

2。最早结束时间：eft=est+持续时间

3。关键路径v0àvk：v0没有依赖；vi依赖于vi-1，vi的est=vi-1的eft；vk的eft是所有任务的最大时间

邻居是白色，就dfs。

不管所依赖的对象是不是白色，都要比较邻居w的eft和自身当前的est！

强连通片SCC

强连通片：任意两个结点之间可达。

算法：1.对原图G做dfs，结点先结束先入栈。栈内时间从小到大排列。

2.将G转置。

3.依次取出栈中结点进行dfs，标记每个强连通片。

无向图DFS

只有TE和BE，没有CE和DE。

变化在于如果是白色：check TE。如果是灰色且w不是parent，check BE.

寻找割点

判断条件：从TE vw回退时，w.back>=v.discoverTime，则v是割点。

寻找桥：从TE vw回退时，w.back>v.discoverTime，则vw是桥。(只去掉了=)

BFS

有向图中：没有DE

无向图中：没有BE和DE

判断二分图

如果没访问过，颜色取反；访问过的话看颜色是否不一样

寻找k度子图

重点题

判断是不是森林？
- 树是无环的连通分量，所以判断无向图无环即可，即没有BE。
- 执行DFS，复杂度为O(n)
计算每个点的cost
- 不管子节点w是什么颜色，如果w的cost更小，赋值给cost[v]
一条边e是否在无向图G中（假设e是边ab）
- 删e，从a或b开始DFS，看能不能搜索到另一点（若有环，a->b至少有两条路径），复杂度为O(m+n)
捣蛋小孩排队
1. 若i->j,i在j前面
  1. 先判断G是否DAG（有back edge则有环，否则无环）；如果有环，则不存在符合条件的排队方法。复杂度O(n+m)
  2. 如果G是DAG，对他执行拓扑排序。根据拓扑排序的性质，如果i到j有边（i hates j），则i会排在j前面，因此拓扑排序是符合要求的排队方法。拓扑排序复杂度为O(n+m)。
  3. 综上，复杂度为O(n+m)
2. 若i->j，i在j前面的行
  1. 对G中的每条边赋给权重1，这样，求G的一条最长路径，就是排队所需要的最少行数。
  2. 问题转化为求G的关键路径问题，使用关键路径算法，复杂度为O(n+m)。
给定一个点是否能到达其他所有点：DFS BFS均可，结束后看有没有白色点
是否存在一个点，能够到达其他所有点：
- 首先执行强连通分支算法SCC,形成收缩图G’ O(n+m)
- 对收缩图，找出G’中入度为0的点 O(n)
供水问题：

端点问题：
- 端点的出度必然为0，而且是唯一的，因为如果有两个出度为0的点，则相互之间不能到达，与端点定义矛盾。假设图的顶点数为n，边数为m。算法为：
  - 扫描全图，找出出度为0的点N。如果这样的点不唯一，则输出“不存在端点”。复杂度为O(n)
    - （这里并不代表他可以到达其他所有点，所以要下面步骤）
  - 构造该图的反向图（即让所有边的方向都反转）。复杂度为**O(n+m)**。
  - 从点N开始，用DFS或BFS遍历，如果可以遍历所有节点，则N为端点，否则，输出“不存在端点”。复杂度为O(n+m)。
  - 综上，复杂度为O(n+m)。
所有路均为单向，希望两两可达：用SCC看G是不是一个强连通分量

如果从某地开始，到哪里都可以返回该地：看在不在Sink SCC（出度为0，只在自己的连通片里走）里面

part6

最小生成树MST

Prim

不断选相邻的最小边：难选（no cycle & small weight）+好检查

每个结点的状态从 unseen->fringe->finished不可逆

取最小的边对应的点加入，看新加的点v的邻居w：

如果w未被发现，加入Fringe;否则看是否要更新权重
$$
T(n,m) = O(nT(getMin)+nT(deleteMin)+ nT(insert)+mT(decreaseKey))
$$

Kruskal

好选（最小的边），难检查（no cycle）不停选最小，然后看在不在一个并查集里面

O(mlogm)=O(mlogn)

MCE

如果存在cut让e在MCE，则e一定在一个MST里面。用反证法证明。

给定源点最短路径SSSP

Dijkstra

拿最小，找邻居，更新dis（不能有负边）

$$
T(n,m) = O(nT(getMin)+nT(deleteMin)+ nT(insert)+mT(decreaseKey))
$$

和Prim式子一样的。

应用1：顶点也有权重了在newWgt那里加入即可

应用2：水管问题 Maximize the min edge weight

应用3：Minimize the max edge weight

part7

所有点对最短路径问题APSP

is there a shortest path

传递闭包：看i->j是否可达。

BF1：暴力枚举所有点

BF2：暴力枚举所有边

BF3：添加长度，上标表示有没有长度<=k的路径

Warshall

O(n^3)

what is the shortest path

Floyd

不能有负环

Solve SSSP and detect negative cycles

Bellman-Ford

和上面有挺大不同：除了起点初始化为0，其他初始化为正无穷。然后进行n-1次松弛计算。

i是指从起点开始，经过几条边。

重点题

最优二叉搜索树：A(low, high, r) is the minimum weighted retrieval cost for subproblem (low, high) when Kr is chosen as the root of its binary search tree.当Kr被选成root时最小的加权代价
最大子串和：分为不用l和用l两种情况
硬币找零 c[i,j] = min (c[i-1, j],1+c[i, j-di])