From 4449d177ce02555d92ee27cd893b13f7f57dca33 Mon Sep 17 00:00:00 2001
From: sshwy <jy.cat@qq.com>
Date: Wed, 6 Jan 2021 08:00:39 +0800
Subject: [PATCH] update math/poly/fft

---
 docs/math/poly/fft.md | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/docs/math/poly/fft.md b/docs/math/poly/fft.md
index 9d0cdad6..da24cc00 100644
--- a/docs/math/poly/fft.md
+++ b/docs/math/poly/fft.md
@@ -204,7 +204,7 @@ $$
 
 时间复杂度 $O(n\log n)$ 。
 
-### 蝴蝶变换
+### 位逆序置换
 
 这个算法还可以从“分治”的角度继续优化。我们每一次都会把整个多项式的奇数次项和偶数次项系数分开，一直分到只剩下一个系数。但是，这个递归的过程需要更多的内存。因此，我们可以先“模仿递归”把这些系数在原数组中“拆分”，然后再“倍增”地去合并这些算出来的值。
 
@@ -215,11 +215,11 @@ $$
 - 两次二分之后 $\{x_0,x_4\} \{x_2, x_6\},\{x_1, x_3\},\{x_5, x_7 \}$ 
 - 三次二分之后 $\{x_0\}\{x_4\}\{x_2\}\{x_6\}\{x_1\}\{x_5\}\{x_3\}\{x_7 \}$ 
 
-规律：其实就是原来的那个序列，每个数用二进制表示，然后把二进制翻转对称一下，就是最终那个位置的下标。比如 $x_1$ 是 001，翻转是 100，也就是 4，而且最后那个位置确实是 4。我们称这个变换为蝴蝶变换。
+规律：其实就是原来的那个序列，每个数用二进制表示，然后把二进制翻转对称一下，就是最终那个位置的下标。比如 $x_1$ 是 001，翻转是 100，也就是 4，而且最后那个位置确实是 4。我们称这个变换为位逆序置换（bit-reversal permutation，国内也称蝴蝶变换）。
 
-根据它的定义，我们可以在 $O(n\log n)$ 的时间内求出每个数蝴蝶变换的结果：
+根据它的定义，我们可以在 $O(n\log n)$ 的时间内求出每个数变换后的结果：
 
-???+ note "蝴蝶变换实现（$O(n\log n)$）"
+???+ note "位逆序变换实现（$O(n\log n)$）"
     ```cpp
     /*
      * 进行 FFT 和 IFFT 前的反置变换
@@ -242,7 +242,7 @@ $$
     }
     ```
 
-实际上，蝴蝶变换可以 $O(n)$ 从小到大递推实现，设 $len=2^k$ ，其中 $k$ 表示二进制数的长度，设 $R(x)$ 表示长度为 $k$ 的二进制数 $x$ 翻转后的数（高位补 $0$ ）。我们要求的是 $R(0),R(1),\cdots,R(n-1)$ 。
+实际上，位逆序变换可以 $O(n)$ 从小到大递推实现，设 $len=2^k$ ，其中 $k$ 表示二进制数的长度，设 $R(x)$ 表示长度为 $k$ 的二进制数 $x$ 翻转后的数（高位补 $0$ ）。我们要求的是 $R(0),R(1),\cdots,R(n-1)$ 。
 
 首先 $R(0)=0$ 。
 
@@ -259,7 +259,7 @@ $$
 1. 考虑 $(1100)_2$ ，我们知道 $R((1100)_2)=R((01100)_2)=(00110)_2$ ，再右移一位就得到了 $(00011)_2$ 。
 2. 考虑个位，如果是 $1$ ，它就要翻转到数的最高位，即翻转数加上 $(10000)_2=2^{k-1}$ ，如果是 $0$ 则不用更改。
 
-???+ note "蝴蝶变换实现（$O(n)$）"
+???+ note "位逆序变换实现（$O(n)$）"
     ```cpp
     // 同样需要保证 len 是 2 的幂
     // 记 rev[i] 为 i 翻转后的值
-- 
2.11.0