算法导论30.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 2 分钟

30.1-1

$\begin{aligned}
&A(x)\cdot B(x)\
=&(7x^3−x^2+x−10)\cdot(8x^3-6x+3)\
=&7\cdot8x^6-8x^5+(-7\cdot 6+1\cdot8)x^4+(7\cdot 3-1\cdot(-6)-10\cdot8)x^3+(-1\cdot 3+1\cdot(-6))x^2+(1\cdot3-10\cdot(-6))-10\cdot 3\
=&56x^2-8x^5-34x^4-53x^3-9x^2+63x-30
\end{aligned}$

30.1-2

假设当前所求多项式为$\displaystyle{A(x)=\sum{i=0}^{n-1} a_ix^{i}}$，使用长除法来计算$q(x)$和$r$。现在考虑消去最高项$a{n-1}$，按照长除法，次高项的系数的变化为$a{n-2}’=a{n-2}+x0\cdot a{n-1}$，从而得到$q(x)$的第$n-2$项系数为$a_{n-1}$，并且消去了$A(x)$的最高次项。往下迭代，直到$A(x)$只剩最低次项的系数即可。

具体过程由EVALUATE-POLY'给出，由于整个过程只有一个for循环，因此其时间复杂度为$\Theta(n)$。

1
2
3
4
5
6
7
EVALUATE-POLY'(A, n, x0)
  Let Q[0 : n - 2] be a new array
  for i = n - 1 downto 1
    Q[i - 1] = A[i]
    A[i - 1] = A[i - 1] + x0 * A[i]
  r = A[0]
  return Q, r

30.1-3

对于多项式$A(x)$中的某个点值对为$(x_0,A(x_0))$，我们可以计算出$A^{\text{rev}}(x)$的某个点值对$\left(\dfrac{1}{x_0},A^{\text{rev}}\left(\dfrac{1}{x_0}\right)\right)$，其中$A^{\text{rev}}\left(\dfrac{1}{x_0}\right)$可以如下进行计算：

$\begin{aligned}
A^{\text{rev}}\left(\dfrac{1}{x0}\right)&=\sum{j=0}^{n-1} a{n-1-j} x_0^{-j}\
&=\sum{j=0}^{n-1} ajx_0^{j-(n-1)}\
&=x_0^{1-n} \sum{j=0}^{n-1} a_jx_0^{j}\
&=x_0^{1-n} A(x_0)
\end{aligned}$

由于每一个点值对的点$x_i$都不为$0$，因此$A(x)$中的每个点值对$(x_i,A(x_i))$对应着$A^{\text{rev}}(x)$的$\left(\dfrac{1}{x_i},x_i^{1-n} A(x_i)\right)$

30.1-4

假设现在存在一个$x$坐标两两不同的点集$P$，其大小为$n-1$。令$P1=P\cup{(x{n-1},y{n-1})},P_2=P\cup{(x{n-1},y{n-1}’)}$，其中$\forall j\in[0,n-2],x{n-1}\neq x{j}$，并且有$y{n-1}\neq y’_{n-1}$。按照定理30.1，节点集合$P_1$可以构造出一个$n$元一次方程组$\mathbf{Xa=y_1}$，并且是存在唯一解向量$\mathbf{a_1}$。类似的，节点集合$P_2$也能够造出一个$n$元一次方程组$\mathbf{Xa=y_2}$，并且存在唯一解向量$\mathbf{a_2}$。由于这两个方程的系数矩阵相同，常数向量不相同，因此解$\mathbf{a_1}$和$\mathbf{a_2}$必定不相同。这确定出了两个不相同的多项式，因此原结论成立。

30.1-5

整个过程由程序INTERPOLATE给出。第1-7行使用普通的乘法计算出多项式$\displaystyle{C(x)=\sum{i=0}^{n-1}(x-x_i)}$的系数，可见是两个for循环的嵌套，因此总共花费了$\Theta(n^2)$的时间。在后面的for循环中，首先调用了一次EVALUATE-POLY'来计算得到$\displaystyle{\sum{j\neq k}(x-xj)}$的系数，花费了$\Theta(n)$的时间，然后使用了$\Theta(n)$的时间计算出了值$\displaystyle{\sum{j\neq k}(x_k-x_j)}$，接下来使用了$\Theta(n)$的时间对$A$的每一个系数都进行了一次更新。因此后面第9-16行的for循环花费的时间也是$\Theta(n^2)$。总而言之，算法INTERPOLATE花费了$\Theta(n^2)$的时间来完成差值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 点集P中的每个元素有两个属性x和y，表示点的坐标。
INTERPOLATE(P, n)
  C = [1]       // 0-index
  for i = 0 to n - 1
    let B[0 : i] be a new array by 0
    for j = 0 to i
      B[i] = B[i] - P[i].x * A[i]
      B[i + 1] = B[i + 1] + A[i]
    C = B
  let A[0 : n - 1] be a new array by 0
  for k = 0 to n - 1
    Q, r = EVALUATE-POLY'(A, n + 1, P[k].x)
    m = 1
    for j = 0 to n - 1
      if j != k
        m = m * (P[k].x - P[j].x)
    for j = 0 to n - 1
      A[j] = A[j] + P[j].y / m * Q[j]
  return A

30.1-6

令$P,Q$分别表示两个多项式，使用点值表示法。我们考虑计算$R=P/Q$。可能出现的错误如下：

  1. 当$Q$中的某些点的$y$坐标为$0$时，直接整除法不可行，需要舍弃掉对应$x$坐标下分别在$P,Q$中的两个点，这时并没有确定结果。

  2. 如果错误1不存在，那么可以使用对应的除法计算出确定结果的点集$R$。但是，$P/Q$不一定是一个多项式（如$P(x)=x^2+1,Q(x)=x+2$），计算出来的点集$R$虽然存在一个多项式进行对应，但是在系数形式下，验算$R\cdot Q$的结果将会发现不为$P$。

因此，只有在$Q$是$P$的一个因子，并且$Q$中不包含$y$坐标为$0$的点，普通的坐标除法才能够给出正确的答案。

30.1-7

对集合$A$定义多项式$\displaystyle{pA(x)=\sum{i=0}^{10n} aix^{i}}$，其中，对于整数$x\in[0,10n]$，如果$x\in A$，那么$a_x=1$，否则$a_x=0$；对集合$B$也可以定义类似的多项式$\displaystyle{p_B(x)=\sum{i=0}^{10n} bix^{i}}$。FFT算法可以以$O(10n\lg(10n))=O(n\lg n)$的时间内计算出多项式$\displaystyle{p_C(x)=p_A(x)\cdot p_B(x)=\sum{i=0}^{20n} c_ix^{i}}$的所有系数。

那么可以求出$C={x:c_x>0,x\in[0,20n]}$。并且，$c_x$表示元素$x$在集合$C$中出现的次数。