算法导论30.1 Exercises 答案

发表于 分类于 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

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}+x_0\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}{x_0}\right)&=\sum_{j=0}^{n-1} a_{n-1-j} x_0^{-j}\\ &=\sum_{j=0}^{n-1} a_jx_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\)。令\(P_1=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-x_j)}\)的系数，花费了\(\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{p_A(x)=\sum_{i=0}^{10n} a_ix^{i}}\)，其中，对于整数\(x\in[0,10n]\)，如果\(x\in A\)，那么\(a_x=1\)，否则\(a_x=0\)；对集合\(B\)也可以定义类似的多项式\(\displaystyle{p_B(x)=\sum_{i=0}^{10n} b_ix^{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\)中出现的次数。