固定一个可以 \(O(1)\) 运算的 effective field \(K\), 并且假设其上的 FFT 时间复杂度为 \(O(N\log N)\). 有序列 \(\{g\}\) 和 \(\{\phi\}\), 如何计算半在线卷积 \(f_n = \phi_i(\sum_{i>0} g_i f_{n-i})\)?
Folklore
把序列拆成两个 \(N/2\) 长度的段, 左边算完了算左边对右边的贡献, 然后算右边. \(T(N) = 2T(N/2)+O(N\log N)\), 解得 \(O(N\log^2 N)\).
能不能再给力一点啊?
把序列拆成 \(b\) 个 \(N/b\) 长度的段, 左边算完了算左边对右边的贡献, 然后算右边.
注意到每块可以直接做 DFT 和 IDFT, 对之后每块的贡献不需要分别算了, 因此时间是 \(T(N) = bT(N/b)+O(N\log N + Nb)\), 取 \(b=\log N\), 解得 \(O\left(\frac{N\log^2 N}{\log\log N}\right)\).
能不能再给力一点啊?
注意到上面的 "块之间的贡献" 也是一个半在线卷积, 时间可以是 \(T(N) = bT(N/b) + (2N/b)T(b) + O(N\log N)\). 注意这里的半在线卷积不是跑完一个跑另一个了, 而是它们一起跑.
取 \(b=\sqrt N\), 递归式是 \(T(N) = 3\sqrt{N} T(\sqrt N) + O(N\log N)\), 复杂度 \(T(N) = O(N(\log N)^{\log 3 / \log 2})\).
能不能再给力一点啊? [vDH07]
如果递归树的叶子数和你根位置的时间复杂度长得不一样, 说明还有平衡的可能.
我们的目标是什么? 答: 上面的递归式每次将 \(N\) 变成了 \(N^{1/2}\) 级别的规模, 我们希望比这个块还要小.
将 \(N\) 理解成一个 \(N^{1/\ell}\) 进制数, 或者说, \(\ell\) 层分块, 对于 \(i\) 到 \(j\) 的贡献, 我们在它们不同的那个最高位位置计算贡献. 这样一来, 有递归的时间复杂度
\[T(N) = (2\ell - 1)N^{1-1/\ell}T(N^{1/\ell}) + O(\ell N\log N). \]注意, 现在 \(N\) 每次变成 \(N^{1/\ell}\) 了, 那么只需要经过 \(\log\log N/\log\ell\) 轮后, 就到了递归树的叶子. 我们把 \(2\ell - 1\) 放成 \(2\ell\), 注意到下一层是
\[2\ell N^{1-\ell}\cdot \ell N^{1/\ell}\log N^{1/\ell} = 2\ell N\log N, \]容易归纳发现第 \(k\) 层的代价是 \(2^k \ell N\log N\), 所以递归的总代价是
\[T(N) = O(2^{\log \log N / \log \ell} \ell N \log N). \]由于
\[2^{\log \log N / \log \ell} \ell = 2^{\frac{\log \log N}{\log \ell} + \log \ell}, \]最优取到 \(\log \ell = \sqrt{\log \log N}\), 有
\[T(N) = O(N\log N 2^{2\sqrt{\log_2 \log N}}). \]根据换底公式, 这也就是 [vDH07] 所写的
\[T(N) = O\left(N\log N \exp \left({2\sqrt{\log 2 \cdot \log \log N}}\right) \right). \][vDH07] Joris van der Hoeven, 2007. New algorithms for relaxed multiplication.
标签：van,log,ell,卷积,复杂度,sqrt,递归,2007,Hoeven From： https://www.cnblogs.com/Elegia/p/17316991.html