Long Luo's Life Notes

By Long Luo

之前的文章 快速傅里叶变换(FFT)算法 和 快速傅里叶变换(FFT)算法的实现及优化 详细介绍了 \(\textit{FFT}\) 的具体实现及其实现。

\(\textit{FFT}\) 优点很多，但缺点也很明显。例如单位复根的实部和虚部分别是一个正弦及余弦函数，有大量浮点数计算，计算量很大，而且浮点数运算产生的误差会比较大。

如果我们操作的对象都是整数的话，其实数学家已经发现了一个更好的方法：快速数论变换 \(\textit{(Number Theoretic Transform)}\) ¹。

快速数论变换(NTT)

\(\textit{FFT}\) 的本质是什么？

• 将卷积操作变成了乘法操作。

是什么让 \(\textit{FFT}\) 做到了 \(O(n \log n)\) 的复杂度？

• 是单位复根。

那有没有什么其他的东西也拥有单位根的这些性质呢？

答案当然是有的，原根² 就具有和单位根一样的性质。

所以快速数论变换 \(\textit{NTT}\) 就是以数论为基础的具有循环卷积性质的，用有限域上的单位根来取代复平面上的单位根的 \(\textit{FFT}\)。

原根

仿照单位复数根的形式，也将原根的取值看成一个圆，不过这个圆上只有有限个点，每个点表达的是模数的剩余系中的值。

在 \(\textit{FFT}\) 中，我们总共用到了单位复根的这些性质：

1. \(n\) 个单位复根互不相同；
2. \(\omega_n^k = \omega_{2n}^{2k}\)；
3. \(\omega_n^{k} = -\omega_n^{k+n/2}\)；
4. \(\omega_n^a \times \omega_n^b = \omega_n^{a+b}\)。

我们发现原根具有和单位复根一样的性质，简单证明³ ：

令 \(n\) 为大于 \(1\) 的 \(2\) 的幂，\(p\) 为素数且 \(n \mid (p-1)\)，\(g\) 为 \(p\) 的一个原根。

我们设 \(g_n = g^{\frac{p-1}{n}}\)：

1. \(g_n^n=g^{n \cdot \frac{p-1}{n}}=g^{p-1}\)

2. \(g_n^{\frac{n}{2}} = g^{\frac{p-1}{2}}\)

3. \(g_{an}^{ak} = g^{\frac{ak(p-1)}{an}} = g^{\frac{k(p-1)}{n}}=g_n^k\)

显然

1. \(g_n^n \equiv 1 \pmod p\)

2. \(g_n^{\frac{n}{2}} \equiv -1 \pmod p\)

3. \((g_n^{k+\frac{n}{2}})^2=g_n^{2k+n} \equiv g_n^{2k} \pmod p\)

证毕。

所以将 \(g_n^k\) 和 \(g_n^{k+\frac{n}2}\) 带入本质上和将 \(\omega_n^{k}\) 和 \(\omega_n^{k+\frac{n}{2}}\) 带入的操作无异。

利用 Vandermonde 矩阵性质，类似 \(\textit{NTT}\) 那样，我们可以从 \(\textit{NTT}\) 变换得到逆变换 \(\textit{INTT}\) 变换，设 \(x(n)\) 为整数序列，则有：

\(\textit{NTT}\) : \(X(m) = \sum \limits_{i=0}^{N}x(n)a^{mn} \pmod M\)

\(\textit{INTT}\) : \(X(m) = N^{-1}\sum \limits_{i=0}^{N}x(n)a^{-mn} \pmod M\)

这里 \(N^{-1}\) ，\(a^{-mn} \pmod M\) 为模意义下的乘法逆元。

当然， \(\textit{NTT}\) 也是有自己的缺点的：比如不能够处理小数的情况，以及不能够处理没有模数的情况。对于模数的选取也有一定的要求，首先是必须要有原根，其次是必须要是 \(2\) 的较高幂次的倍数。

By Long Luo

之前的文章 快速傅里叶变换(FFT)算法 详细介绍了 \(\textit{FFT}\) 的具体实现，也实现了分治版的 \(\textit{FFT}\)。

分治版 \(\textit{FFT}\) 代码很容易理解，但递归会消耗 \(O(\log n)\) 的栈空间，同时代码实现中还有很多优化空间，这篇文章我们就来优化 \(\textit{FFT}\) 下的实现。

Cooley-Tukey FFT Algorithm

\(\textit{Cooley-Tukey FFT Algorithm}\) ¹ 通过使用分治算法² 实现将复杂问题简单化。

FFT 分治过程

具体操作流程可以分为 \(3\) 步：

1. Divide：按照奇偶分为 \(2\) 个子问题。
2. Conquer：递归处理 \(2\) 个子问题
3. Combine：合并 \(2\) 个子问题。

蝴蝶操作

分治的前 \(2\) 步之前已经详细讲述过了，第 \(3\) 步合并操作是通过蝴蝶操作(Butterfly Operations)来实现的，其示意图如下所示：

蝴蝶操作可能会让人看了一头雾水，不过没关系，我们一步一步来，彻底弄懂她！

空间优化

回顾之前的 递归版代码 ，在合并这一步，这一层有 \(n\) 项需要处理，我们新建了一个数组 \(y(n)\)，这是为什么呢？

我们可以复用之前的 \(y_e\) 或 \(y_o\) 数组以降低空间复杂度吗？

先看下合并需要做的操作：

\[ y(k) = y_e(k) + \omega_{n}^{k} \cdot y_o(k + \frac{n}{2}) \]

\[ y(k + \frac{n}{2}) = y_e(k) - \omega_{n}^{k} \cdot y_o(k + \frac{n}{2}) \]

很明显，我们如果复用 \(y_e\) 或 \(y_o\) 数组的话，那 \(y(k)\) 和 \(y(k + \frac{n}{2})\) 至少有一个数据会受影响，所以我们需要额外的 \(y(n)\) 数组来存储数据。

那么有没有办法来做到复用 \(y_e\) 或 \(y_o\) 数组呢？

当然可以！

我们只要将修改下合并顺序，加入一个临时变量 \(t = \omega_{n}^{k} \cdot y_e(k + \frac{n}{2})\) ，合并过程就可以在原数组中进行：

\[ cd \; t = \omega_{n}^{k} \cdot y_e(k+\frac{n}{2}) \]

\[ y_e(k+\frac{n}{2}) = y_e(k) - t \]

\[ y_e(k) = y_e(k)+t \]

这样就可以原地进行了，不再需要额外数组。

By Long Luo

Leetcode 396. 旋转函数 题解。

方法一： 暴力法

思路与算法

很容易想到的方法是遍历，使用 \(2\) 个循环，很明显最多只能有 \(len\) 次旋转，因为对称性，所以数组下标可能会 \(>= len\)，所以要取余 \((i+j) \mod len\) 。

每次旋转更新最大值，时间复杂度为 \(O(N^2)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// BF time: O(n^2) space: O(1)
   public int maxRotateFunction(int[] nums) {
       int len = nums.length;
       if (len <= 1) {
           return 0;
       }

       int ans = Integer.MIN_VALUE;
       for (int i = 0; i < len; i++) {
           int sum = 0;
           for (int j = 0; j < len; j++) {
               sum += j * nums[(i + j) % len];
           }

           ans = Math.max(ans, sum);
       }

       return ans;
   }

复杂度分析：

• 时间复杂度：\(O(N^2)\) ，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。

• 空间复杂度：\(O(1)\) 。

方法二： 动态规划

思路与算法：

方法一会超时，其实观察旋转数组的变化：

\[ F(0) = 0 \times nums[0] + 1 \times nums[1] + \ldots + (n - 1) \times nums[n-1] \]

\[ F(1) = 1 \times nums[0] + 2 \times nums[1] + \ldots + 0 \times nums[n-1] = F(0) + \sum_{i=0}^{n-1}nums[i] - n \times nums[n-1] \]

我们很容易发现相邻旋转的递推关系：

\[ F(k+1) = F(k) + \sum_{i=0}^{n-1}nums[i] - n \times nums[n-k], 0 \le k \lt n \]

从\(F(0)\)出发，迭代计算出不同的\(F(k)\)，并求出最大值。

很容易使用DP写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// DP time: O(n) space: O(n)
public int maxRotateFunction_dp(int[] nums) {
    int len = nums.length;
    if (len <= 1) {
        return 0;
    }

    int[] dp = new int[len];
    int sum = 0;
    for (int i = 0; i < len; i++) {
        dp[0] += i * nums[i];
        sum += nums[i];
    }

    int ans = dp[0];
    for (int i = 1; i < len; i++) {
        dp[i] = dp[i - 1] + sum - len * nums[(len - i) % len];
        ans = Math.max(ans, dp[i]);
    }

    return ans;
}

观察上述代码，我们发现dp[]数组只是记录数值，实际上可以将空间复杂度优化到\(O(1)\)。

By Long Luo

This article is the solution 4 Approaches: Recursion, Iteration, BFS and DFS of Problem 617. Merge Two Binary Trees .

Here are 4 approaches to solve this problem in Java: Recursion, Iteration, BFS and DFS.

Recursion

Method 1: New Tree

We can create a new Tree, each \(\texttt{TreeNode}\) value is sum of two nodes.

1
2
3
4
5
6
7
8
9
10
11
12

public static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    }
    if (root2 == null) {
        return root1;
    }
    TreeNode merged = new TreeNode(root1.val + root2.val);
    merged.left = mergeTrees(root1.left, root2.left);
    merged.right = mergeTrees(root1.right, root2.right);
    return merged;
}

Analysis

• Time Complexity: \(O(min(m, n))\)
• Space Complexity: \(O(min(m, n))\)

Method 2

Traverse both the given trees in a PreOrder style.

At every step, check if the current node exists for both the trees. If one of these children happens to be null, we return the child of the other tree to be added as a child subtree to the calling parent node in the first tree.

We can add the values in the current nodes of both the trees and update the value in the current node of the first tree to reflect this sum obtained.

Then we call the \(\texttt{mergeTrees()}\) with the left children and then with the right children of the current nodes of the two trees.

At the end, the first tree will represent the required resultant merged binary tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static TreeNode mergeTrees_rec(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    }
    if (root2 == null) {
        return root1;
    }

    if (root1 != null) {
        root1.val += root2.val;
        root1.left = mergeTrees_rec(root1.left, root2.left);
        root1.right = mergeTrees_rec(root1.right, root2.right);
    }

    return root1;
}

Analysis

• Time Complexity: \(O(min(m, n))\)
• Space Complexity: \(O(min(m, n))\)

By Long Luo

207. 课程表

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public boolean canFinish(int numCourses, int[][] prerequisites) {
    if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0) {
        return true;
    }

    int[] indegree = new int[numCourses];
    for (int[] pre : prerequisites) {
        indegree[pre[0]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            queue.offer(i);
        }
    }

    while (!queue.isEmpty()) {
        Integer currId = queue.poll();
        numCourses--;
        for (int[] pre : prerequisites) {
            if (pre[1] == currId) {
                indegree[pre[0]]--;
                if (indegree[pre[0]] == 0) {
                    queue.offer(pre[0]);
                }
            }
        }
    }

    return numCourses == 0;
}

复杂度分析

• 时间复杂度：\(O(V + E)\) ，其中 \(n\) 为字符串长度。
• 空间复杂度：\(O(V)\) 。哈希表和字符串均需要存储 \(n\) 个元素。

参考资料

1. Topological Sorting
2. 拓扑排序
3. Topological Sort (Indegree)
4. Topological Sort (DFS)