最大间隔区间

问题情景： 给定在一个服务器上复制文件的n个无序时间戳$x_{1},x_{2}, x_{3}, ...,x_{n}$.找到不进行复制文件的最大时间间隔。 本质：找到无序数值集合中，排序后相邻元素的最大差值。 即：

• 对时间戳数组进行排序O($NlogN$)
• 线性扫描一遍数组，找到最大差值O(N) 故总时间复杂度为O(NlogN)

3-sum问题：

问题情境： 给定n个不同的整数，找到3个数字的和为0。

朴素算法：O($n^{3}$)

结合target_sum问题(双指针算法，单层O(N)):

• 先对整个数组进行排序O(NlogN)
• 选取一个$a_{i}$，在剩余的数字中执行一个target-sum问题，其中target = -$a_{i}$。O(N). 故整体时间复杂度为O($NlogN + N^{2}$) = O($N^{2}$)

分治的主定理

若时间复杂度满足式子：

case1: 若c $> log_{b}^{a}$，则T(n) = $\theta (n^{c})$ case2: 若c = $log_{b}^{a}$，则$T(n) = \theta (n^{c}logn)$ case3：若c < $log_{b}^{a}$，则T(n) = $\theta (n^{log_{b}^{a}})$

主定理的收缩条件： 当递归满足形式：

• 若$\alpha + \beta < 1$，所有子问题的规模加起来要小于原问题，即原问题收缩，则有T(N) = O(N)
• 若$\alpha + \beta = 1$，则T(N) = O(NlogN)
• 若$\alpha + \beta >1$，则不是线性的，一般大于O(NlogN)

计数逆序对

逆序对： 索引i < j的同时，对应的值$a_{i} > a_{j}$

问题： 给定一系列数据，找到有多少对逆序对。 merge and sort实现：

• 输入：左右两半按升序排序完成
• 初始化A为空集，算法维持左指针i和右指针y
• 若L(i) <= R(j), L(i)不会与R(j)之后的任意元素形成逆序对。将L(i)加入到A的尾部，i指针后移
• 若L(i) > R(j)，则($L(i), R(j)$)均为逆序对。将R(j)加入逆序对，且j指针后移
• i或j到达终点时循环结束，此时将剩余元素直接加入A，返回A和逆序对 同时返回的A序列为排序好的数列。 时间复杂度为O(N) 故有递推式为：

即T(N) = O(NlogN)

最近点对问题

给定平面上的n个点坐标，寻找具有最短欧氏距离的一对点。

算法实现：

• 画一条分界线，大致保证每一侧有$\frac{n}{2}$个点。O(NlogN)
• 设$\delta_{1}$ = 左半边的最短点对；$\delta_{2}$ = 右半边的最短点对；设$\delta = min\{\delta_{1}, \delta_{2}\}$ 2T(N/2)
• 删除距离分界线L距离超过$\delta$的点 O(N)
• 按照y坐标对剩余的点进行排序 O(NlogN)
• 按照y坐标对每一个点进行扫描，比较每一个点和其11个相邻节点的距离，更新$\delta$ O(N)
• 返回最终的$\delta$ 故得到递推式：

即T(N) = O(N$log^{2}N$)

整数相乘

已知x与y分别为两个n位的整数，计算n * y： 朴素算法：

得到

所以T(N) = O($N^{2}$)

加速算法：

得到递推式为：

得到$T(N) = O(N^{log_{2}^{3}})$