算法导论30.2 Exercises 答案

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

30.2-1

\(\begin{aligned} \omega_{n}^{n/2} &= (e^{2\pi i/n})^{n/2}\\ &=e^{\pi i}\\ &=e^{2\pi i/2}\\ &=\omega_2\\ &=\cos \pi+i\sin\pi\\ &=-1 \end{aligned}\)

30.2-2

经过暴力计算，可得\(\text{DFT}_4(A)\)的结果如下：

\(\begin{aligned} y_0&=0\cdot (\omega_{4}^0)^0+1\cdot (\omega_{4}^0)^1+2\cdot (\omega_{4}^0)^2+3\cdot (\omega_{4}^0)^3\\ &=6\\ y_1&=0\cdot (\omega_{4}^1)^0+1\cdot (\omega_{4}^1)^1+2\cdot (\omega_{4}^1)^2+3\cdot (\omega_{4}^1)^3\\ &=0+i-2-3i\\ &=-2i\\ y_2&=0\cdot (\omega_{4}^2)^0+1\cdot (\omega_{4}^2)^1+2\cdot (\omega_{4}^2)^2+3\cdot (\omega_{4}^2)^3\\ &=0+1\cdot(-1)+2-3\cdot(-1)\\ &=-2\\ y_3&=0\cdot (\omega_{4}^3)^0+1\cdot (\omega_{4}^3)^1+2\cdot (\omega_{4}^3)^2+3\cdot (\omega_{4}^3)^3\\ &=0-1\cdot(-i)+2\cdot(-1)+3\cdot i\\ &=2i-2 \end{aligned}\)

即有\(\text{DFT}_4(A)=(6,-2i,-2,2i-2)\)。

30.2-3

如下是递归计算\(\text{FFT}((-10,1,-1,7,0,0,0,0),8)\)的结果：

\(\begin{aligned} &\text{FFT}((-10,1,-1,7,0,0,0,0),8)\\ &\qquad \text{FFT}((−10,−1,0,0),4)\\ &\qquad\qquad \text{FFT}((-10,0),2)\\ &\qquad\qquad\qquad \text{FFT}((-10),1)\\ &\qquad\qquad\qquad\qquad y=(-10)\\ &\qquad\qquad\qquad \text{FFT}(0,1)\\ &\qquad\qquad\qquad\qquad y=(0)\\ &\qquad\qquad\qquad y=(-10,10)\\ &\qquad\qquad \text{FFT}((-1,0),2)\\ &\qquad\qquad\qquad \text{FFT}((-1),1)\\ &\qquad\qquad\qquad\qquad y=(-1)\\ &\qquad\qquad\qquad \text{FFT}((0),1)\\ &\qquad\qquad\qquad\qquad y=(0)\\ &\qquad\qquad\qquad y=(-1,1)\\ &\qquad\qquad y=(-11,-10-i,-9,-10+i)\\ &\qquad \text{FFT}((1,7,0,0),4)\\ &\qquad\qquad \text{FFT}((1,0),2)\\ &\qquad\qquad\qquad \text{FFT}((1),1)\\ &\qquad\qquad\qquad\qquad y=(1)\\ &\qquad\qquad\qquad \text{FFT}(0,1)\\ &\qquad\qquad\qquad\qquad y=(0)\\ &\qquad\qquad\qquad y=(1,11)\\ &\qquad\qquad \text{FFT}((7,0),2)\\ &\qquad\qquad\qquad \text{FFT}((7),1)\\ &\qquad\qquad\qquad\qquad y=(7)\\ &\qquad\qquad\qquad \text{FFT}((0),1)\\ &\qquad\qquad\qquad\qquad y=(0)\\ &\qquad\qquad\qquad y=(7,7)\\ &\qquad\qquad y=(8,1+7i,-6,1-7i)\\ &\qquad y=(-3,-(10+3\sqrt{2})+(4\sqrt{2}-1)i,-9-6i,(-10+3\sqrt{2})+(4\sqrt{2}+1)i,-19,(-10+3\sqrt{2})-(4\sqrt{2}+1)i,-9+6i,-(10+3\sqrt{2})+(1-4\sqrt{2})i) \end{aligned}\)

类似的，可以计算出\(\text{FFT}((3,-6,0,8,0,0,0,0),8)\)的结果为

\((5,(3-7\sqrt{2})+\sqrt{2}i,3-14i,(3+7\sqrt{2})+\sqrt{2}i,1,(3+7\sqrt{2})-\sqrt{2}i,3+14i,(3-7\sqrt{2})-\sqrt{2}i)\)

通过点值表示法将各自的值直接相乘，可以得到乘积的点值表示为

\((-15,(4+62\sqrt{2})+(-65+9\sqrt{2})i,-111+108i,(4-62\sqrt{2})+(65+9\sqrt{2})i,-19,(4-62\sqrt{2})+(-65-9\sqrt{2})i,-111-108i,(4+62\sqrt{2})+(65-9\sqrt{2})i)\)

最终通过逆快速傅里叶变换得到答案为\((-30,63,-9,-53,-34,-8,56,0)\)。

30.2-4

给出的代码为FFT-INV。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
FFT-INV(y, n)
  if n == 1
    return y
  ωn = exp(-2 * π * i / n)
  ω = 1
  y-even = (y_0, y_2, ..., y_{n - 2})
  y-odd = (y_1, y_3, ..., y_{n - 1})
  a-even = FFT-INV(y-even, n / 2)
  a-odd = FFT-INV(y-odd, n / 2)
  for k = 0 to n / 2 - 1
    a_k = (a-even_{k} + ω * a-odd_{k}) / n
    a_{k + n / 2} = (a-even_{k} - ω * a-odd_{k}) / n
    ω = ω * ωn
  return a

30.2-5

参考引理30.5，首先证明三分引理：如果\(n\)是一个\(3\)的倍数，那么这\(n\)个\(n\)次单位复数根的立方的集合就是\(n/3\)个\(n/3\)次单位复数根的集合。

接下来证明这个引理，考虑\((\omega_{n}^{k+n/3})^3,(\omega_{n}^{k+2n/3})^3,(\omega_{n}^{k})^3\)之间的关系，有

\(\begin{aligned} (\omega_{n}^{k+n/3})^3&=\omega_n^{3k}\omega_n^n\\ &=\omega_n^{3k}\\ &=(\omega_n^{k})^3\\ (\omega_{n}^{k+2n/3})^3&=\omega_n^{3k}\omega_n^{2n}\\ &=\omega_n^{3k} \end{aligned}\)

根据引理30.3和上面的结论，可以得到\((\omega_{n}^{k+n/3})^3=(\omega_{n}^{k+2n/3})^3=(\omega_{n}^{k})^3=\omega_{n}^{3k}=\omega_{n/3}^{k}\)，最终引理成立。

那么接下来令\(\displaystyle{A(x)=\sum_{i=0}^{n-1} a_ix^{i}}\)，并且定义\(\displaystyle{A^{(k)}(x)=\sum_{i=0}^{n/3-1} a_{3i+k}x^{i}}\)，其中\(k\in\{0,1,2\}\)。那么可以将\(A(x)\)写成：

\[A(x)=A^{(0)}(x^3)+xA^{(1)}(x^3)+x^2A^{(2)}(x^3)\]

那么一个规模为\(n\)的问题被分解成\(3\)个规模为\(n/3\)的问题。令\(T(n)\)表示规模为\(n\)的问题的运行时间，那么有

\[T(n)=3T(n/3)+\Theta(n)\]

按照主定理的第二个条件，可以得到\(T(n)=\Theta(n\lg n)\)。

如下是满足这个情况时的算法FFT3：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
FFT3(y, n)
  if n == 1
    return y
  ωn = exp(2 * π * i / n)
  ω = 1
  a0 = (a_0, a_3, ..., y_{n - 3})
  a1 = (a_1, a_4, ..., y_{n - 2})
  a2 = (a_2, a_5, ..., y_{n - 1})
  y0 = FFT3(a0, n / 3)
  y1 = FFT3(a1, n / 3)
  y2 = FFT3(a2, n / 3)
  for k = 0 to n / 3 - 1
    y_{k} = y0_{k} + ω * y1_{k} + ω^2 * y2_{k}
    y_{k + n / 3} = y0_{k} + (ω * ω_{3}^{1}) * y1_{k} + (ω * ω_{3}^{1})^2 * y2_{k}
    y_{k + 2 * n / 3} = y0_{k} + (ω * ω_{3}^{2}) * y1_{k} + (ω * ω_{3}^{2})^2 * y2_{k}
    ω = ω * ωn
  return a

\(\star\) 30.2-6

不难发现\(\gcd(m,\omega)=1\)，因为\(m\)为奇数，且\(\omega\)只包含因子\(2\)。因此\(\omega\in \mathbb{Z}_m^{\ast}\)。接下来考虑\(\omega\)在\(\mathbb{Z}_m^\ast{}\)中的阶\(k=\lambda_m(\omega)\)，也就是最小的整数使得\(\omega^{k}\equiv 1\pmod m\)成立。

考虑\(\dfrac{2^{tk}-1}{2^{tn/2}+1}=\dfrac{2^{tk}+2^{tn/2}}{2^{tn/2}+1}-1=2^{tn/2}\cdot\dfrac{2^{tk-tn/2}+1}{2^{tn/2}+1}-1\)，当\(k=n\)时，\(\dfrac{2^{tk-tn/2}+1}{2^{tn/2}+1}=1\)，即保持了整除，且分子是分母的最小倍数，因此有\(k=n\)，即\(\lambda_m(\omega)=n\)。

由于\(\lambda_m(\omega)=n\)的存在，因此由元素\(\omega\)在\(\mathbb{Z}_m\)所生成的群\(\langle\omega\rangle\)是一个循环群。那么定义\(\omega^j=2^{tj}\bmod m\)。

接下来证明引理/定理/推论30.3，30.4，30.5，30.6, 30.7在\(\langle\omega\rangle\)中是成立的。

引理30.3的证明：考虑\(n\)的某个因子\(d\)，令\(\omega'=2^{td}\)，那么有\(\omega'^{k/d}\equiv 2^{tk}\equiv \omega^{k}\pmod m\)。因此原结论成立。

推论30.4的证明：\(\omega^{n/2}\equiv 2^{tn/2}\equiv -1\pmod {m}\)，因此结论得证。

引理30.5的证明：\((\omega^{k+n/2})^2\equiv\omega^{2k+n}\equiv\omega^{2k}\omega^n\equiv\omega^{2k}\equiv (\omega^k)^2\pmod m\)，因此结论得证。

引理30.6的证明：当\(n\nmid k\)时，有\(\omega^k\not\equiv 1\pmod m\)成立。证明过程和原本的定理30.6的计算过程一致，原结论得证。

定理30.7的证明：此时\(V_{n}^{-1}\)的第\(j\)行第\(k\)列的项为\(\omega^{-jk}\cdot n^{-1}\bmod m\)。由于\(n\)是\(2\)的幂，但是\(m\)是奇数，因此\(\gcd(n,m)=1\)，因此在\(\mathbb{Z}_m\)中存在\(n\)的逆元\(n^{-1}\)，结论中的写法是成立的，考虑\([V_{n}^{-1}V_n]_{kk}\)的值，有\([V_{n}^{-1}V_n]_{kk}\equiv\displaystyle{\sum_{j=0}^{n-1}}(\omega^{-jk}\cdot n^{-1})(\omega^{jk'})\equiv n^{-1}\cdot \sum_{j=0}^{n-1}\omega^{j(k'-k)}\pmod p\)。其余证明过程类似，因此原结论成立。

在\(\langle\omega\rangle\)中，首先计算好\(\omega\)的幂\(\omega^i\)。由于\(\langle\omega\rangle\subseteq \mathbb{Z}_m^{\ast}\subseteq \mathbb{Z}_m\)，可见\(\omega^i\in \mathbb{Z}_m\)。因此\(\displaystyle{y_k=\sum_{i=0}^{n-1}a_i(\omega^k)^i}\)的整个计算过程是封闭的，DFT过程是正确定义的。

对于DFT的逆过程，由于\(\gcd(\omega,m)=1\)，因此\(\omega\)在\(\mathbb{Z}_m\)中也存在逆元\(\omega^{-1}\)，容易验证\(\langle \omega\rangle=\langle\omega^{-1}\rangle\)，因此\(\displaystyle{a_k=n^{-1}\sum_{i=0}^{n-1}y_i(\omega^{-k})^i}\bmod m\)的整个计算过程是封闭的，即DFT的逆过程是正确定义的。

最终原结论成立。

30.2-7

我们将考虑构造出多项式\(\displaystyle{P(x)=\prod_{i=0}^{n-1}(x-z_i)}\)，并考虑计算它的系数。

可见，\(P(x)\)是由\(n\)个\(1\)次多项式同时相乘。令\(m\)是大于等于\(n\)的最小二次幂，那么\(P(x)\)也可以看成是由\(m\)个\(1\)次项同时相乘。

接下来考虑讲相邻的每\(2\)个\(k\)次多项式因子相乘，得到一个新的\(2k\)次多项式进行存储，这个过程需要进行\(\dfrac{m}{2k}\)次，得到\(\dfrac{m}{2k}\)个\(2k\)次多项式因子，接下来将\(k\)扩增成\(2\)倍继续操作即可。具体算法由GEN-POLY-BY-ZERO-POINT给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
GEN-POLY-BY-ZERO-POINT(z, n)
  let m be a power of 2 s.t. m >= n and m is minium 
  let P[0 : m - 1] be a new array
  for i = 0 to m
    if i < n
      P[i] = [-z[i], 1]
    else
      P[i] = [1, 0]
  b = m
  while b > 1
    l = n / b * 2
    let Q[0 : b / 2 - 1] be a new array
    for i = 0 to b / 2 - 1
      for k = 0 to l
        INSERT(P[i * 2], 0)
        INSERT(P[i * 2 + 1], 0)
      Q[i] = IFFT-INV(FFT(P[i * 2], 2 * l) ⋅ FFT(P[i * 2 + 1], 2 * l), 2 * l)
    b = b / 2
    P = Q
  return P[0, 0 : n]

在每次while循环中，需要进行\(\dfrac{m}{2k}\)次规模大小为\(O(k\lg k)\)的FFT，因此单次while循环的时间复杂度为\(\dfrac{m}{2k}\cdot O(k\lg k)=O(m\lg k)=O(m\lg m)\)。由于需要进行\(\lg m\)次while循环，并且\(m=\Theta(n)\)因此GEN-POLY-BY-ZERO-POINT的时间复杂度为\(m\cdot O(m\lg m)=O(m\lg^2m)=O(n\lg^2n)\)。

\(\star\) 30.2-8

构造如下两个多项式：\(\displaystyle{B(x)=\sum_{j=0}^{n-1}b_jx^j}\)和 \(\displaystyle{C(x)=\sum_{j=0}^{n-1}C_jx^j}\)，其中\(b_j=a_jz^{j^2/2},c_j=z^{-j^2/2}\)。使用FFT算法可以求出\(D(x)=B(x)\cdot C(x)\)。令\(\displaystyle{D(x)=\sum_{j=0}^{n-1}d_jx^j}\)。那么可以知道：

\(\begin{aligned} d_k&=\sum_{j=0}^{k} b_jc_{k-j}\\ &=\sum_{j=0}^{k} (a_jz^{j^2/2})(z^{-(k-j)^2/2}) \end{aligned}\)

对于\(\forall k\in[0,n)\)，在以\(O(n\lg n)\)的时间计算好值\(d_k\)的值之后，只需要令\(y_k=z^{k^2/2}\cdot d_k\)即可。此外多项式\(B(x),C(x)\)可以以\(O(n\lg n)\)的时间构造出来，因此最终整个过程仅使用\(O(n\lg n)\)的时间完成。大概过程由CHIRP-TRANSFORM给出。

1
2
3
4
5
6
7
8
9
10
11
12
CHIRP-TRANSFORM(A, n, z)
  let m be a power of 2 s.t. m >= n and m is minium 
  let B[0 : 2 * m - 1], C[0 : 2 * m - 1] be new arrays by 0
  for j = 0 to n - 1
    w = exp(z, j * j / 2)
    B[j] = A[j] * w
    C[j] = 1 / w
  D = IFFT-INV(FFT(B, 2 * l) ⋅ FFT(C, 2 * l), 2 * l)
  let Y[0 : n - 1] be a new array
  for k = 0 to n - 1
    Y[k] = exp(z, k * k / 2) * D[k]
  return Y