算法导论3.2 Exercises 答案

发表于 2022-11-28 更新于 2023-07-03 分类于算法导论阅读次数：本文字数： 2.6k 阅读时长 ≈ 2 分钟

3.2-1

由于$f(n)\ge 0,g(n)\ge 0$，因此可以构造出如下不等式：

$\begin{aligned} &f(n)\le \max\{f(n),g(n)\}&(1)\\ &g(n)\le \max\{f(n),g(n)\}&(2)\\ &f(n)+g(n) \ge \max\{f(n),g(n)\}&(3) \end{aligned}$

根据式子$(1),(2)$，可以得到$\dfrac{f(n)+g(n)}{2}\le \max\{f(n),g(n)\}$。利用这条不等式和式子$(3)$，可以得到：

\[0\le\dfrac{f(n)+g(n)}{2}\le \max\{f(n),g(n)\}\le f(n)+g(n) \]

其中，$c_1=\dfrac{1}{2},c_2=1$，根据$\Theta$符号的定义得到${f(n),g(n)}=(f(n)+g(n)) $

这句话可能的本意是：算法$A$的时间复杂度至少为$\Theta(n^2)$。根据符号$O$的定义，$n^2$是内部这些函数的上界。也就是说，这句话是说明算法$A$的时间复杂度至少是以$n^2$为上界中的一个。因此这种说法毫无意义。

$2^{n+1}=O(2^n)$

要求构造出一对$n_0,c$使得对于所有的$n\ge n_0$，满足$0\le 2^{n+1}\le c\cdot 2^n$。

可以将第二个不等式化简成$c\ge 2$，那么我们能够成功构造出$c=n_0=2$。

$2^{2n}\neq O(2^n)$

要求构造出一对$n_0,c$使得对于所有的$n\ge n_0$，满足$0\le 2^{2n}\le c\cdot 2^n$。

可以将第二个不等式化简成$c\ge 2^n$，由于$2^n$的无限增长，不存在$n_0$，使得当$n>n_0$时，仍然满足$c\ge 2^n$，由此得出答案。

充分性：对于$f(n)=\Theta(g(n))$，存在正整数$n_0,c_1,c_2$使得对于所有$n\ge n_0,0\le c_1g(n)\le f(n)\le c_2 g(n)$成立。

将如上不等式提取出$0\le c_1 g(n)\le f(n)$，那么$(c_1,n_0)$的存在性说明$f(n)=\Omega(g(n))$

将如上不等式提取出$0\le f(n)\le c_2g(n)$，那么$(c_2,n_0)$的存在性说明$f(n)=O(g(n))$

最终，充分性成立。

必要性：

对于$f(n)=\Omega(g(n))$，存在正数$n_1,c_1$使得对于所有使得对于所有$n\ge n_1,0\le c_1 g(n)\le f(n)$成立。

对于$f(n)=O(g(n))$，存在正数$n_2,c_2$使得对于所有使得对于所有$n\ge n_2,0\le f(n)\le c_2 g(n)$成立。

构造出$n'=\max(n_1,n_2)$，那么对于所有$n\ge n',0\le c_1 g(n)\le f(n),0\le f(n)\le c_2 g(n)$均成立，也就是$0\le c_1g(n)\le f(n)\le c_2 g(n)$。

那么新构造出的$(c_1,c_2,n')$说明$f(n)=\Theta(g(n))$

最终，必要性成立。

假设算法的最好运行时间为$T_l(n)$，最坏运行时间为$T_r(n)$，那么对于算法的任意运行时间$t(n)$位于区间$[T_l(n),T_r(n)]$中。

根据题目所给的条件，得到$T_l(n)=\Omega(g(n)),T_r(n)=O(g(n))$，那么根据$\Omega,O$符号的定义，分别有：

存在正数$n_1,c_1$使得对于所有使得对于所有$n\ge n_1,0\le c_1 g(n)\le T_l(n)$成立。

存在正数$n_2,c_2$使得对于所有使得对于所有$n\ge n_2,0\le T_r(n)\le c_2 g(n)$成立。

令$n'=\max(n_1,n_2)$，那么对于所有$n\ge n'$，以下不等式成立：

\[0\le c_1g(n)\le T_l(n)\le t(n)\le T_r(n)\le c_2g(n)\]

根据$\Theta$符号的定义，构造出的$(n',c_1,c_2)$说明$t(n)=\Theta(g(n))$。

令$f(n)=o(g(n))\cap \omega(g(n))$。

根据$\omega$符号的定义：存在正数$n_1,c_1$使得对于所有使得对于所有$n\ge n_1,0\le c_1 g(n)< f(n)$成立。

根据$o$符号的定义：存在正数$n_2,c_2$使得对于所有使得对于所有$n\ge n_2,0\le f(n) < c_2g(n)$成立。

令$n'=\max(n_1,n_2)$，那么对于所有$n\ge n'$，以下不等式成立：

\[c_1g(n)<f(n)<c_2g(n)\]

根据$o,\omega$的定义，随着$n$增长，它不能在保证$c_1 g(n)< f(n)$的同时，又满足$f(n)< c_2g(n)$。因此这样的$f(n)$不存在，原集合为空集。

集合$\Omega(g(n,m))$是满足以下条件的所有函数$f(n,m)$：存在正数$c,n_0,m_0$，对于所有$n\ge n_0\lor m\ge m_0$，等式$0\le cg(n,m)\le f(n,m)$成立。

集合$\Theta(g(n,m))$是满足以下条件的所有函数$f(n,m)$：存在正数$c_1,c_2,n_0,m_0$，对于所有$n\ge n_0\lor m\ge m_0$，等式$0\le c_1g(n,m)\le f(n,m)\le c_2g(n,m)$成立。