算法之美第二章 习题

02 Jun 2014 by LelouchHe

前注

暂时忽略所有的fft题目,这部分和复数搭边的还没有搞得太懂,暂时放下先

2.1

在上一篇中我们已经看到了几种不同的乘法分治方法,可以简单的进行unroll即可计算

分治算法不难想到,关键是如何像书本中那样,得到4变3的优化.我这里也没有太多好的想法,大体上可能还是跟着主定理,想方法减少子问题规模或者子问题数量,但当初的灵机一动,是如何也想不出来的

jeff的笔记上讲过一些当年的背景趣闻,可以参看一下

2.2

问题即证明$\exists k, n \leq b ^ k \leq b n$,两边同时对b取对数,得$\log _ b n \leq k \leq \log _ b (b n) = \log _ b n + 1$,可以看到,不等式两边差一,所以中间必然存在满足条件的整数k

ps:遇到类似带有乘幂的问题,一般有两个想法,一是利用乘幂的性质($a ^ x a ^ y = a ^ {x + y}, (a ^ x) ^ y = a ^ {x y}$),二是利用对数,转化成对应的四则运算.二者本质是一样的,只是对数比较方便判断和比较而已

2.3

本题引入了另一种求解递归式的方法,相比递归树而言,这个更适合计算,但也略微不太直观

需要注意的是,这些递推公式都没有递归终点,这样的公式是完整的,这里可以假设$T(1) = O(1)$,但实际的操作过程中,需要根据实际情况进行分析,关键是永远不要忘了递归终点

a

展开对应的递推式,得

$k = \log n$可以最后化简公式,得$T(n) = n ^ {\log _ 2 3} O(1) + \frac{4}{3} c n ^ {\log _ 2 3} - 2 c n = O(n ^ {\log _ 2 3})$

同主定理的结论一致

ps:计算复杂度,同以前的高数类似,关键不仅在于变换形式,还有适当情况下的忽略和补位,这个还是需要多多积累经验才能看到的

b

$T(n) = T(n - 1) + c = T(n - 2) + 2 c = \dots = T(1) + c n = O(n)$

ps:上述两个问题,除了$T(1)$的假设之外,其实我们还有一个假设,即每次展开的常数是相同的(都是c),但在实际问题中,这个也是不一定成立的,所以还是需要谨慎

2.4

算法A: $T(n) = 5 T(n / 2) + O(n) = O(n ^ {\log _ 2 5})$

算法B: $T(n) = 2 T(n - 1) + O(1) = O(2 ^ n)$

算法C: $T(n) = 9 T(n / 3) + O(n ^ 3) = O(n ^ 3)$

要选择的话,应该选择算法A

2.5

a

$T(n) = 2 T(n / 3) + 1 = O(n ^ {\log _ 3 2})$

b

$T(n) = 5 T(n / 4) + n = O(n ^ {\log _ 4 5})$

c

$T(n) = 7 T(n / 7) + n = O(n \log n)$

d

$T(n) = 9 T(n / 3) + n ^ 2 = O(n ^ 2 \log n)$

e

$T(n) = 8 T(n / 2) + n ^ 3 = O(n ^ 3 \log n)$

f

$T(n) = 49 T(n / 25) + n ^ {3 / 2} \log n = O(n ^ {3 / 2} \log n)$

g

$T(n) = T(n - 1) + 2 = O(n)$

h

$T(n) = T(n - 1) + n ^ c = O(n ^ {c + 1})$

计算过程比较巧妙,可以参照1.4的解法

所以得到了结论

i

$T(n) = T(n - 1) + c ^ n = \sum c ^ i$

若$c = 1$,则$T(n) = O(n)$

若$c > 1$,则$T(n) = \frac{c ^ n - 1}{c - 1} = O(c ^ n)$

j

$T(n) = 2 T(n - 1) + 1 = 2 ^ n + \sum 2 ^ i = 2 ^ {n + 1} - 1 = O(2 ^ n)$

k

$T(n) = T(\sqrt {n}) + 1 = T(\sqrt[4] {n}) + 2 = T(\sqrt[2 ^ k] {n}) + k$

假设$T(c) = O(1)$,此时$\sqrt[2 ^ k] {n} = c \Rightarrow k = \log \log _ c n = O(\log \log n)$,所以$T(n) = O(\log \log n)$

2.6

(暂时忽略)

2.7

ps:复数计算是个很头痛的地方,需要谨慎

2.8-2.10

(暂时忽略)

2.11

设$Z = X Y$,根据矩阵乘法规则,有$Z(i, j) = \sum X(i, k) Y(k, j)$,然后分块来看结果矩阵

以左上角为例,$i \in [0, n / 2), j \in [0, n / 2)$,对应的分别是A/B和E/G(因为$k \in [0, n)$),根据乘法法则,可以看出左上角的结果是$A E + B G$

剩余可以以此类似可得证明

2.12

类似复杂度分析,$f(n) = 2 f(n / 2) + 1 = \Theta (n)$

2.13

a

可以画图看看,有$B _ 3 = 1, B _ 5 = 2, B _ 7 = 5$

如果n为偶数,则无法构成满二叉树了,因为除去根节点外,每层的节点都是偶数(包括0),所以总的节点数是奇数

b

递归的表示已经有了($B _ n$),现在来考虑问题的分解

减2

一个自然的想法是将问题规模减2,即$B _ n \Rightarrow B _ {n - 2}$,以此来得到子问题

• 递归终点 a中已经有了几个基本case,为了简单期间,我们可以设$B _ 1 = 1$作为终点
• 合并子问题 已知$B _ {n - 2}$,如何求解$B _ n$呢?一个自然的想法是给多出的2个节点找到一个父节点即可,此处的父节点就是原满二叉树$B _ {n - 2}$的叶子节点.这样,我们就需要计算出可能的叶子节点的数目,就是新的满二叉树的数目

但是存在一个细节,即相同的满二叉树只能算作一个.比如计算$B _ 7$时,三层的满二叉树有两种构建方法(二层左/右),但这样的二叉树只能计算一个.所以我们还需要求解类似对称/镜像的二叉树数量

这样看来,就比较复杂了,我们可以换换思路

分子树

树形结构的特点,有一个自然的减小规模的方式,即以根节点拆分为两个子树

• 递归终点 此处最自然的就是$B _ 1 = 1$的情况,作为终点
• 合并子问题 子问题是什么呢?我们必须表达成$B _ x$的形式(问题性质必须类似).没有好的办法之前,枚举是唯一的方法.节点总数为n,左子树节点从1到n-1(设为i),那么右子树节点数相应的是n-1-i.已知左右子树的数目,原树的数目利用乘法原理即可得到,有$B _ n = \sum B _ i B _ {n - 1 - i}$

这样的合并子问题是没有重复的,因为左右子树数目不一样,必然是不同的满二叉树,没有”减2”时的重复

ps:看$B _ n$的递推公式,可以联想到类似的Catalan数,不同的是$B _ n$对于偶数n的结果为0,因此无法直接利用Catalan数的公式和性质

先补充一下该数的性质.$C _ n = \sum C _ i C _ {n - 1 - i} = \frac{4 n - 2}{n + 1} C _ {n - 1} = \frac{1}{n + 1} {2 n \choose n}$,

我们怎么把$B _ n$和$C _ n$联系起来呢?把$B _ n$的下标中的偶数去掉即可,即

同Catalan数进行比较

而且,$B _ 1 = 1 = C _ 0$,可得,$B _ {2 k + 1} = C _ k$,这样我们就可以将已知的Catalan数性质公式拿来直接使用了

求和的小技巧

$\sum$求和时,有两个关键点,一个是求和的式子(内部),另一个是求和定义域.在变换时,两个都要注意,第一次变换的时候,我也是很长时间不得要领,混淆了很长一段时间,还是数学功底差啊

另外,遇到间隔求和(类似本题的奇数项),一个常见的方法是将间隔变换成连续,这样更容易发现规律

c

由b可知,$B _ {2 k + 1} = C _ k = \frac{4 k - 2}{k + 1} C _ {k - 1} = \frac{4 k - 2}{k + 1} B _ {2 k - 1}$,当n一定时,$B _ n \geq 4 B _ {n - 1}$,所以满足$B _ n = 2 ^ {\Omega {n}}$

2.14

问题比较简单,但是要从分治的角度来思考这个问题

问题的表示可以先简单的表达为当前元素的个数,即$(n)$,然后考虑如何减小问题规模

规模减1

即每次首先挑出一个元素,然后递归的解决规模小1的问题

• 递归终点 自然的想法是$(1)$,此时什么都不需要操作
• 合并子问题 目前已知$(n - 1)$和一个元素(假设是$a _ n$),此时,只需要遍历已知的$(n - 1)$序列,把和$a _ n$重复的元素排除掉,那么剩下的就是无重复序列了

复杂度应该是$T(n) = T(n - 1) + O(n) = O(n ^ 2)$,哈哈,不满足要求诶.

规模减半

还是惯用的减小规模的办法,将原序列分解为两个子序列,分别处理再合并

• 递归终点 同样的是$(1)$,此时不需要处理
• 合并子问题 已知2个$(n / 2)$,即2个无重复元素的序列,此时,唯一可能的重复出现在这两个序列之间,那么分别遍历,然后将重复元素排除饥渴

此时复杂度是$T(n) = T(n / 2) + O(n ^ 2) = O(n ^ 2)$,哈哈,还是不满足要求

思考

为什么没有得到一个满足要求的算法呢?可以看到,简单的减小问题规模,而不做额外的处理,其结果和bf直接遍历基本没有什么区别.我们需要做一些额外的工作,利用每次分解/合并的信息,来优化算法

优化1

规模减半的解法中,合并代价是$O(n ^ 2)$,因为处理的是无序序列,如果两个子序列有序,那么只需要$O(n)$就可以完成目标了.限制为有序,则在合并子问题阶段,不仅需要遍历比较,还需要类似mergesort,输出新的有序序列,这个同样是$O(n)$

那么此时的复杂度是$T(n) = 2 T(n / 2) + O(n) = O(n \log n)$,满足条件了

优化2

合并时的处理,同样可以放在分解时进行.类似quicksort,我们不再完全二分,而是将序列分解为一小一大的有序序列块,这样的分解操作需要$O(n)$,那么再处理完各自的子序列后,原序列不可能由重复元素(有序),那么合并也就很trival了

此时的复杂度是$T(n) = O(n) + 2 T(n / 2) = O(n \log n)$,同样满足要求

优化3

规模减一的时候,首先是要遍历序列,判断是否和挑选出来的$a _ n$重复,可以想象到,子问题$(n - 1)$则是挑选出$a _ {n - 1}$,然后重复遍历判断重复.第一次遍历的信息,根本没有在后续使用到,虽然二者遍历的几乎是同一个序列(后续的序列只小不大),一个自然的想法就是先预处理,把序列信息整合起来,使后续可以直接使用

最自然的想法就是利用hashmap,保存元素和出现次数,然后在遍历序列,把唯一的元素跳出即可.(当然,剩下的一些单遍历优化就是边边角角,此处不赘述)

这样的复杂度是$T(n) = O(n)$,但空间复杂度也成了$O(m)$,即hashmap的大小了

总结

合并子问题其实不止是合并工作,在合并子问题阶段,已知规模小的问题的解答,即只要规模小于当前的规模,都能得解,那么我们就可以完全任意的来分解问题了.也就是说,主要工作不一定在真正合并的那一刻,也可以在为了合并而分解问题的那一刻

就那mergesort和quicksort来说,mergesort就是随意分解,但合并时复杂(合并承担主要工作),但quicksort则是小心分解,使得合并非常trival(分解承担主要工作).分治法无非就是这两个步骤,在思考合并子问题时,要着重思考两点,一是是否需要仔细分解问题,二是是否需要仔细合并问题.简单的问题可能一个即可,但有的问题则是需要两头开弓才行

预处理在分治算法中,也有很重要的用途.因为分解之后的子问题是原问题的一部分,所以必然由一些性质是共享的,当在分治求解时,发现一些信息在被重复使用/计算,就可以想想能否通过预处理,来优化这部分的时间.当然,最后可能就直接像优化3一样,脱离来分治的路子了,但我们是要解题,所以也是一个好的现象

2.15

quicksort/quickselect的分解关键,算法主要维护几个区间:

• [0, small): 小于v
• [small, equal): 等于v
• (big, n - 1]: 大于v

代码如下:

void partition(vector<int>& S, int v) {
    int small = 0;
    int equal = 0;
    int big = S.size() - 1;
    while (equal <= big) {
        if (S[equal] < v) {
            swap(S[small++], S[equal++]);
        } else if (S[equal] == v) {
            equal++;
        } else {
            swap(S[equal], S[big--]);
        }
    }
}

2.16

看到$O(\log n)$的复杂度要求,第一个想法应该是可能需要用到二分查找,但同二分不同,这里的n是不确定的,因此,为了使用二分,我们首先应该在$O(\log n)$的复杂度下,得到序列的边界

自然的想法是遍历,找到$\infty$最初的位置即可,但这样的复杂度就是$O(n)$,而且,如果真的这样的话,直接遍历寻找x即可,没必要多此一举了

另一种想法就是二分的变体,以$2 ^ i$为间隔遍历序列,遇到$\infty$就可以在最后一个区域进行二分查找边界.这样的复杂度是$O(\log n)$

当然,更进一步的,查找边界可以和查找元素一起,虽然复杂度是一致的,但可以减小常数项

代码如下:

// A是无穷数组(暂时表示下下)
// 保证: 数组内部没有INFTY
int find(int A[], int x) {
    if (A[0] > x) {
        return -1;
    } else if (A[0] == x) {
        return 0;
    }

    int r = 0;
    int step = 1;

    while (A[r] != INFTY && A[r] < x) {
        step <<= 1;
        r += step;
    }

    int l = r - step;
    
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (x < A[m]) {
            r = m - 1;
        } else if (x > A[m]) {
            l = m + 1;
        } else {
            return m;
        }
    }

    return -1;
}

出现$\log n$的场景

看到$O(\log n)$,就要想到一系列可以引入对数的运算过程.一般来讲,对数很少直接出现在问题求解中,往往是通过其他过程引入(比如本题的二分).有以下几种情况:

1. 为了达到n,需要对2进行自乘的次数
2. n减小到1,需要折半的次数
3. 二进制表示n需要的位数
4. n个节点的完全二叉树的深度(平衡树也是类似的量级)
5. $\sum \frac{1}{i}$与$\log n$相差常数

再次遇到对数,或碰到以上类似的场景,要会分析

2.17

又看到$\log n$,还是会联想到二分,关键是找到如何二分(不像上一题,没有边界,但二分标准是trival的)

思考如果$A[i] > i$,数组下标是按1递增的,数组值A[j]同样是有序递增且不相同,那么其递增幅度至少为1,那么此时,对于$j > i$,有

所以i后的元素是不可能存在可能的解的,此时只需要检验前方即可.

对于$A[i] < i$的情况是类似的,这样,我们有了可以用来二分的标准,使用二分即可.代码如下:

int find_fix_point(vector<int>& A) {
    int l = 0;
    int r = A.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (m < A[m]) {
            r = m - 1;
        } else if (m > A[m]) {
            l = m + 1;
        } else {
            return m;
        }
    }

    return -1;
}

二分的应用

可以看到,对于这个没有任何显式顺序的问题,二分也是适用的,可见二分适用范围之广.在我看来,只要问题边界明确(或可求),问题可能解之间有隐式偏序关系,即可利用二分求解

• 边界明确 亦即求解空间是有限的已知范围.一般来说,题目会明确的交待解空间大小(比如常规的二分),但有的题目,如2.16,虽然没有显式的指出范围,但经过处理可以边界(普通遍历或二分变体).其实2.16的变体基本就是处理边界未知但有序的一个基本手段
• 隐式偏序 类似普通二分问题,可以利用二分求解的问题需要有序,但这个序不一定是大小关系,而是可以将原问题划分为几个聚类的性质(如果是两个,就是二分)

说的可能比较难懂,其实我自己也没有彻底的搞明白这个,只是说说自己的看法

原问题的解需要满足特定的性质集,该性质集可以将解空间重复的划分为不同的聚类,可能的解空间不断减小规模,直到得到最终解

上面是个比较泛化的描述,将性质集定义为大小顺序,聚类数量为2,聚类划分是序列区间,那么我们就得到了普通的二分

但二分不是唯一的划分方法,按照这个泛化的理论,可以n分,而且每次划分的性质不一定需要一致.使用二分只不过是因为一般来说,二分的聚类容易描述(用区间即可),递归求解非常方便而已

当然,理论和实际是有很大差距的,话虽说的好听,但实际操作一下才能真正体会.还需要通过练习来培养眼光和感觉

Matrix67的这篇博客和这篇博客是很好的学习二分的材料,可以参看一下

2.18

普通的二分需要处理三种情况(大于/小于/相等),遇到相等就直接退出了.但此处我们只能区分两种情况,所以就只能完全的将序列划分到底,直到最后才能判断是否存在满足条件的解了(因为中间只能使用比较操作),此时的操作次数至少$\Omega (\log n)$

其实这也是利用二分查找边界情况的变体,需要熟悉

2.19

a

第一次合并复杂度是$O(n + n) = O(2 n)$,第二次是$O(2 n + n) = O(3 n)$,依次类推,第i次合并是$O((i + 1)n)$,总共需要$k - 1$次合并,所以总的复杂度是$O(\sum ^ {k - 1} (i + 1) n) = O(\frac{(k - 1)(k + 2)}{2} n) = O(k ^ 2 n)$

b

可以看到,a的合并过程并不理想,逐渐添一的方法不是最优,可以参照分治的原则,每次把待合并数组对半划分,分别合并,然后再合并新的2个序列即可

这样的复杂度是$T(k) = 2 T(k / 2) + k n = O(k \log k n)$

思考

为什么折半的复杂度比两两合并要低呢?画图可以直接的看到,两两合并的复杂度相当于阶梯图形下的面积,而折半合并则相当于阶梯图形下三角形的面积(可以计算看看),明显的折半比两两合并少了那k个阶梯的转折

这些转折是哪里来的呢?或者说折半合并是如何消除这些多余的呢?

可以将合并抽象为二进制的表达,两两合并相当于加一操作,但折半合并相当于乘2递增,当所求结果一样(都是k)时,显然,乘2递增是快于加一操作的

2.20

由于M较小,所以可以采用另一种著名的排序–桶排序方法来操作序列.遍历序列值,统计间隔M内各个元素的数量,然后再遍历M输出即可

这个不受限于$\Omega (n \log n)$下限的约束,是因为此排序方法不进行比较操作(比较排序才受限与此的),单纯的通过统计来排序.统计的复杂度一般都是线性的,所以在M较小时,可以看做是线性排序

2.21

a

两边都会增加其值,所以最小的只能是中项$\mu _ 1$了

b

公式比较容易得证,如果没有hint的话,只能求函数最小值的方式来求解了.hint的话,展开利用平均数$n \mu _ 2 = \sum x _ i$的性质即可证明

c

$\mu _ 3$和序列元素最大距离最小,这显然是最大最小值的平均数,遍历序列即可同时求得最大最小值,所以复杂度是$O(n)$

2.22

这个基本就是leetcode上的Median of Two Sorted Arrays,我们可以参考那道题目的解法

先是确定题目的表示,一个直观的想法是利用三元组$(m, n, k)$,m是数组A的个数,n是数组B的个数,k是要寻找的序数

解法1

一个自然的想法是通过分解尝试寻找第k个数,由于牵扯到两个数组,所以各选$k / 2$个进行划分,这样第k个数就可能从二数组划分的边界产生

• 递归终点 显然,一方为空时,就可以直接求解了.此处假设$m < n$,那么$(0, n, k)$就可以直接输出B数组的第k个数即可.由于划分需要定位第$k / 2$个数,所以当$k = 1$时,是不合理的(第0个数是什么道理啊..),所以当$k = 1$时,即最小的数,我们可以直接比较A/B数组的首个元素即可,也就是$(m, n, 1)$时,直接输出二者最小值
• 合并子问题 已知规模小的求解方法,怎么得到原问题的解呢?从A/B各选第$k / 2$个数进行比较,有如下情况
  1. $A _ i = B _ i$时,二者左边恰好有k个数(我们专门凑的呗),那么这两个就是所求解
  2. $A _ i < B _ i$时,$A _ i$左边的数肯定不会是问题的解,所以我们直接求解剩下的有半部分即可$(m - k / 2, n, k / 2)$,问题规模减小,我们已知如何求解的
  3. $A _ i > B _ i$时同理

这样,每次分解要么直接求解,要么问题规模减小$k / 2$(理想情况,因为有可能m/n没有那么大,不过这种情况的下一步有可能直接取k了),所以复杂度是$O(\log k)$

解法2

除去找第k个数的方法,我们还可以尝试折半,也就是先不考虑k,而是先折半,再判断

• 递归终点 同于解法一,$(0, n, k)$直接输出数组B的第k个即可.此处不需要求解$k / 2$,所以对k没有要求
• 合并子问题 类似解法一,只不过分别选取了$m / 2$和$n / 2$个数而已.假设此时的$A _ i < B _ i$(相反情况类似),此时的$A _ i$的序数$k _ A \in [m / 2, m / 2 + n / 2]$,$B _ i$的序数$k _ B \in [m / 2 + n / 2, m + n / 2]$.比较k与$m / 2 + n / 2$的关系,有
  1. $k < m / 2 + n / 2$,$B _ i$右边的肯定不满足要求了,所以直接抛弃,求解$(m, n / 2, k)$即可
  2. $k > m / 2 + n / 2$,$A _ i$左边的肯定不满足要求了,所以直接抛弃,求解$(m / 2, n, k - m / 2)$即可
  3. 相等情况,可随意抛弃

这样每次分解,至少会将m/n减半,所以复杂度是$O(\log m + \log n)$

一点思考

本题有几点供我们思考的地方

1. 分解问题的方式 本题的两种解法其实类似,不过一个是寻找k来分解,另一个是先分解再寻找k.先分解后定位k是一个管用的思路,二分之类的都是遵从这个思路
2. 递归终点的由来 其实我们很早就提到过,终点有两种来源,一是逻辑上的终点,比如数组为空时,直接输出第k个数,这是逻辑上的最简单情况;另一个是算法运行的边界情况,比如解法1的$k = 1$,此时无法挑出对应的A/B项,所以只能单独拿出来计算.当然,有可能这也是逻辑上的边界,可能需要进一步的解释

2.23

注意题目中”主元素”的含义,是要超过半数,即大于$n / 2$,至少$n / 2 + 1$.思考问题时一定要记住这点,否则纠结于一半会很难搞清楚状况

a

将序列划分为$A _ 1$和$A _ 2$,并递归求解其各自主元素.如果二者主元素不存在,则表示原序列主元素不存在;设存在主元素,则遍历原序列,判断该主元素是不是原序列主元素即可

复杂度是$T(n) = 2 T(n / 2) + O(n) = O(n \log n)$

b

根据hint,将原序列两两分组,相同的保留一个,不同的全部删除

因为配对后最多保留一个元素,所以最多留下$n / 2$个元素

主元素至少有$n / 2 + 1$个,其他元素最多有$n / 2 - 1$,除去和主元素配对的,其他元素最多剩余$(n / 2 - 2) / 2 = n / 4 - 1$,所以主元素剩余至少$n / 4 + 1$.所以在分解后的序列中,主元素仍然为主元素,问题得解

复杂度是$T(n) = T(n / 2) + O(n) = O(n)$

思考

该问题有一个经典的变体,即编程之美的课后练习题,找到3个出现频率大于$1 / 4$的数

类似的问题都有类似的巧妙解法,但是线性解法确实很难在一开始就想到(除非事先遇到过),所以需要仔细想想该类问题的解决

这个有点像概率问题,初碰到毫无头绪,看了答案才知道很trick,再碰到就可能trival了

未完待续

2.24

a

快排是经典算法,需要非常熟悉

// 调用方式:
// quicksort(v, 0, v.size() - 1);
void quicksort(vector<int>& v, int l, int r) {
    if (l < r) {
        int p = pick_pivot(v, l, r);
        int m = partition(v, l, r, p);
        quicksort(v, l, m - 1);
        quicksort(v, m + 1, r);
    }
}

int pick_pivot(vector<int>& v, int l, int r) {
    return l + rand() % (r - l + 1);
}

int partition(vector<int>& v, int l, int r, int p) {
    swap(v[r], v[p]);

    int i = l;
    int j = l;
    while (j < r) {
        if (v[j] < v[r]) {
            swap(v[i], v[j]);
            i++;
        }
        j++;
    }
    swap(v[i], v[r]);

    return i;
}

b

快排的最理想情况是什么?自然是每次pick_pivot都恰好挑选到了中位数,将原序列分为相等的子序列,此时$T(n) = O(n) + 2 T(n / 2) = O(n \log n)$

最坏情况呢?自然是选取到了最值,子序列严重不平衡,有$T(n) = O(n) + T(n - 1) = O(n ^ 2)$

c

由于每种划分都是等可能的,所以$T(i) + T(n - i)$出现的概率都是$1 / n$,所以整体的期望自然是$T(n) = O(n) + \frac{1}{n} \sum (T(i) + T(n - i))$,得

上下二式相减,可得

展开到$T(0) = O(1)$即可

可以得到其期望复杂度

随机算法思考

对于选择固定pivot(比如最后一个元素)的快排,最坏情况是遇到有序序列,这样,复杂度直接就是b中的$O(n ^ 2)$

这种情况发生的概率不大($1 / (n !)$),但对于非随机输入来说,还是很有可能的.所以一个自然的想法就是将输入先随机排列一次,再进行快排,这样就让最坏情况的概率恒定的保持在最小,保证了即使对于特殊情况,也能得到期望复杂度.随机排列原序列,和此处的随机挑选pivot,道理是一样的

因此可以看到,对于平均复杂度很好,但最坏情况复杂度很差的算法,可以适当的引入随机因子,让最坏的输入以恒定的小概率出现,从而降低算法整体的复杂度

有人会说,不用随机也行,因为本来最坏输入的情况就是那么小啊.其实不然,如果使用算法的一方碰到的情景都是最坏情况怎么办?怎么和他们解释平均/期望复杂度很好呢?

背后的道理就是不要信任任何输入,而是要通过预处理,将输入性质规范化.此处的预处理使用了随机因子,目的是避免最坏输入而已

2.25

a

由于最后的操作是$z ^ 2$,所以$z = (10 ^ {n / 2})$,这样缺失的部分是折半操作(题目说n是2的幂次方,所以肯定可以折半),z = pwr2bin(n / 2);

复杂度是$T(n) = T(n / 2) + O((n / 2) ^ a) = O(n ^ a)$

b

显然的性质是$x = x _ l 10 ^ {n / 2} + x _ r$,所以需要分别计算$x _ l, x _ r$和$10 ^ {n / 2}$,然后利用加法/乘法计算即可

缺失的步骤是return fastmultiply(dec2bin(x_l), pwr2bin(n / 2)) + dec2bin(x_r);

复杂度是$T(n) = 2 T(n / 2) + O(n ^ a) = O(n ^ a)$

2.26

应该不正确,乘积不会因为相等而减少运算量的

2.27

a

要想减少乘法次数,只能像数乘一样利用性质进行变换

这样,得到了5次乘法的形式

b

分治法的重要标识是子问题性质相同,规模减小.利用这样的5次乘法的分解,得到的相乘子矩阵和原问题不相同,即相乘的两个矩阵不一定相同,所以无法这样来完成矩阵的平方

c

还是各种变换技巧,利用矩阵平方来计算不同矩阵乘积.好吧,具体的变换技巧我还没有琢磨出来,继续钻研

2.28

对原矩阵运算变换,得

可见,复杂度为$T(n) = O(n) + 2 T(n / 2) = O(n \log n)$

2.29

a

简单的展开即可得到结果

b

每次循环进行一次乘法操作和一次加法操作,共循环$n$次,所以$NM(n) = 2 n, NA(n) = 2 n$

Horner准则是最优的多项式求解方法

2.30

(暂时忽略)

2.31

a

设$d = gcd(a, b)$,然后分情况讨论

a/b均为偶数

由题,$d = a x + b y = 2 a ‘ x + 2 b ‘ y$,所以d肯定也是偶数,得$d = 2 d ‘ = 2 (a ‘x + b ‘ y) \Rightarrow d ‘ = a ‘ x + b ‘ y$,所以$d ‘ = gcd(a ‘, b ‘)$,替换一下即可得到第一种情况

a为奇数,b为偶数

由题,$a = d x, b = d y$,由于b是偶数,有$b = 2 b ‘ = d y$,由于a是奇数,所以d不可能是偶数,所以y必须是偶数,有$b = 2 b ‘ = d 2 y ‘ \Rightarrow b ‘ = d y ‘$,因此$d = gcd(a, b ‘)$,得第二种情况

a/b均为奇数

由题,$gcd(a, b) = gcd(a - b, b)$,由于a/b均为奇数,所以$a - b$为偶数,此时应用第二种情况,可得第三种情况

这样就覆盖了所有情况,得证

b

按照a中的递归公式即可.不过a中的公式没有给出重要的递归终点,需要补充完善,即$gcd(a, 0) = a$

int gcd(int a, int b) {
    if (a < b) {
        return gcd(b, a);
    }

    if (b == 0) {
        return a;
    }

    if (a % 2 == 0 && b % 2 == 0) {
        return 2 * gcd(a / 2, b / 2);
    } else if (a % 2 == 0 && b % 2 != 0) {
        return gcd(a / 2, b);
    } else if (a % 2 != 0 && b % 2 == 0) {
        return gcd(a, b / 2);
    } else {
        return gcd((a - b) / 2, b);
    }
}

最开始的大小判断是为了避免重复判断.应该有更简化的写法,还需要思考

c

每次递归,位数会减一,所以最多递归$2 n$次,每次递归过程中,只进行奇偶判断(使用&操作),乘2(左移),除2(右移),减法,对于大数来说,复杂度都是$O(n)$,所以总的复杂度为$O(n ^ 2)$,优于Euclid算法

思考

此处计算gcd,我们并没有直接从数论的角度来求解,相反,采用了分治的想法(典型的折半分解).当然,其中分解/合并时,仍然需要利用数学性质来证明,但分治确实是我们走向解决问题的第一步,有了这一步,才有了构造出来的递归公式,才有了后续的证明

能不能想到分治,是解决问题的第一步;有没有对应的数学知识来构造和证明,是解决问题的第二步.一步都不能少

2.32

a

因为$d _ l \geq d$,所以L中点对最小距离为d.如果在$d \times d$的矩形区域内存在4个点,那么这4个点必然是矩形区域的4个顶点.此时,矩形区域内任意点与4顶点间距都小于d,所以不可能存在.问题得证

b

如果最近点对在L/R中,问题已经得证,所以假设最近点对分别在L/R之间

由于已经有d存在,所以我们只检验以x值为轴,左右宽度为d的矩形区域.针对任意区域内点,检测长度最长亦为d,形成了$d \times 2 d$的矩形.根据a的结论,这里最多有8个点(左4右4),因此针对1个点,最多需要检验7个点即可

故此处算法是可行的

c

由算法描述可知,$T(n) = O(n) + 2 T(n / 2) + O(n \log n) + O(n) = 2 T(n / 2) + O(n \log n)$,展开即可,可得

d

可以看到,主要的瓶颈在于每次的排序操作,我们可以对点进行预处理,提前排序好,然后就可以通过$O(n)$来选取对应的点,这样有$T(n) = 2 T(n / 2) + O(n) = O(n \log n)$

2.33

a

M为非0矩阵,则至少有一项不为0,如果$M v = 0$,则与该非零项相乘的必须为0,这个的概率为$1 / 2$,所以$M v = 0$的概率至多为$1 / 2$

b

利用矩阵运算性质,$A B v = C v \Rightarrow (A B - C) v = 0$,有两种情况,要不然$A B = C$,这是需要我们证明的,要不然就是类似a的情况,非零矩阵乘积为0,概率小于$1 / 2$.所以如果$A B \neq C$,则$A B v = C v$的概率小于$1 / 2$

因此可以通过k个随机v,来验证,如果全部都有$A B v = C v$,那么$A B \neq C$的概率就小于$\frac{1}{2 ^ k}$,随着k的增大而减小

计算$M v$的复杂度是$O(n ^ 2)$,故计算$A B v = A (B v) = A v ‘$复杂度也是$O(n ^ 2)$,总的复杂度是$O(k n ^ 2)$

2.34

虽然不懂3SAT的具体解法,但就本题而言,可以这样思考:首先选择有$x _ 1$(包括正/反)的子句(最多可能$2 (20 \choose 2) = 380$个组合,$x _ 1$分正负,然后剩下的$x _ 2 ~ x _ {11}$包括正反,选择2个),然后分别给组合内的元素枚举即可.选定真假后,递归的处理剩余的即可

这样的复杂度是$T(n) = T(n - 1) + O(1) = O(n)$,只不过常数可能比较大