算法导论30.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 6.1k 阅读时长 ≈ 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}
y0&=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)$写成：

那么一个规模为$n$的问题被分解成$3$个规模为$n/3$的问题。令$T(n)$表示规模为$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}Vn]{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}Cjx^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}
dk&=\sum{j=0}^{k} bjc{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