Homework 3

Problem 1

首先对 应满足的性质进行分析，若 是一个合数，即

则

故 的最小性不符，因而 必然为质数，从而 即不整除 的最小质数

由于 是不整除 的最小质数代表所有小于 的质数都是 的因子，因此设 为第 个质数，有

这里的量级分析来自第一切比雪夫函数的结论

因此一方面，如果对 的大小有一定的限制，则可以直接取小范围内的质数逐一检验整除性，如 时，只需要取到第 16 个素数 53 即可，这可以被认为是 的

另一方面，如果 的大小无限制，则直接从 开始逐一用辗转相除法检验，其复杂度严格为

算法即

Problem 2

由题有

故

由于 是 模 的逆元，故

因此只需要尝试 和 两种可能即可（若非整数则直接舍去）

对于每一种可疑的 ，都有

即 是

的两个根

使用求根公式求解后，若两个根均为整质数即可判断分解成功，因此整体复杂度为 次加减乘除开方运算与 次判断素数运算，是十分高效的

Problem 3

记 ，基于 的定义，猜测

另设原式中 的常数上界为 ，即

假设对于所有 ，该猜测成立

则代入原递归式（为书写方便没有考虑取整的影响）得：

又因为

代入上式得：

由拉格朗日中值定理，对函数 ，存在 使得：

故：

要使

也成立，只需保证多余的项小于等于零即可，即：

由于 ，只需 充分大即可

综上，由数学归纳法得证 ，即：

Problem 4

考虑 ，由于 不相同且递增，由整数的离散性，有

故直接二分判断即可

答案即

Problem 5

Task 1

根据题目定义，算法无法直接使用数组的值，对数组进行 query 当且仅当根据数组值之间的序关系对 进行更新，因此前 步中所有 condition 都相同的情况下，算法的表现是确定性的，也即 在两种情况下是相同的

Task 2

在课上， 的代码如下 区别在于没有使用索引而是直接用了 的对应切片，但将这里的 的输入改为左右端索引，输出（也即 的输入）变为记录索引的数组

则此时用到 数组的位置就只有 中比较 和 了，因而属于 strongly comparison based

Task 3

这种 sorting 本质上是一个 decision tree 结构，而每次 compare 只会得到一个二分类，因此 decision tree 是一个二叉树。而这个树需要能遍历所有结果，每种结果即一个 的 permutation，因此共有 个结果，设决策树高度为 ，则有

由 公式，

因此得到

Task 4

一方面，这个运算是线性（）的，另一方面，这不改变每个条件语句均引出一个二分类的性质，因此即使加入了这一运算，搜索树依然是二叉树，因此 Task 3 的结论不变

Problem 6

这其实即计数排序的原理

1. 对 到 遍历，得到 和 ，也即得到了
2. 准备 到 共 个 bucket
3. 再次从 到 遍历，把每个元素的索引值 放入 bucket 中
4. 从 bucket 遍历到 ，按顺序将其中的元素索引输出为

复杂度为

的下界在此不适用是因为这里元素的可能种类有限，可以直接进行 分类，所以并不是单纯基于比较的分类方式，而一般的排序不存在这种性质，就必须用元素的两两比较分类