By Long Luo

机器学习中需要训练大量数据，涉及大量复杂运算，例如卷积、矩阵等。这些复杂运算不仅多，而且每次计算的数据量很大，如果能针对这些运算进行优化，可以大幅提高性能。

一、矩阵乘法

假设 \(A\) 为 \(m \times p\) 的矩阵，\(B\) 为 \(p \times n\) 的矩阵，那么称 \(m \times n\) 的矩阵 \(C\) 为矩阵 \(A\) 与 \(B\) 的乘积，记作 \(C = AB\)，称为矩阵积（\(\textit{Matrix Product}\)）。

其中矩阵 \(C\) 中的第 \(i\) 行第 \(j\) 列元素可以表示为：

\[ (AB)_{ij} = \sum_{k=1}^{p}{a_{ik}b_{kj}} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{ip}b_{pj} \]

如下图所示：

假如在矩阵 \(A\) 和矩阵 \(B\) 中，\(m=p=n=N\)，那么完成 \(C=AB\) 需要多少次乘法呢？

1. 对于每一个行向量 \(r\) ，总共有 \(N\) 行；
2. 对于每一个列向量 \(c\) ，总共有 \(N\) 列；
3. 计算它们的内积，总共有 \(N\) 次乘法计算。

综合可以看出，矩阵乘法的算法复杂度是：\(O(N^3)\)。

二、Strassen算法

那么有没有比 \(O(N^{3})\) 更快的算法呢？

1969年，Volker Strassen 提出了第一个算法时间复杂度低于 \(O(N^{3})\) 矩阵乘法算法，算法复杂度为 \(O(n^{log_{2}^{7}})=O(n^{2.807})\) 。从下图可知，\(\textit{Strassen}\) 算法只有在对于维数比较大的矩阵( \(N > 300\) ) ，性能上才有很大的优势，可以减少很多乘法计算。

\(\textit{Strassen}\) 算法证明了矩阵乘法存在时间复杂度低于 \(O(N^{3})\) 的算法的存在，后续学者不断研究发现新的更快的算法，截止目前时间复杂度最低的矩阵乘法算法是 Coppersmith-Winograd 方法的一种扩展方法，其算法复杂度为 \(O(n^{2.375})\) 。

三、Strassen原理详解

假设矩阵 \(A\) 和矩阵 \(B\) 都是 \(N \times N (N = 2^{n})\) 的方矩阵，求 \(C = AB\) ，如下所示：

\[ \begin{aligned} A = \left [\begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} \right] \\ B = \left [\begin{matrix} B_{11} & B_{12} \\ B_{21} & B_{22} \\ \end{matrix} \right] \\ C = \left [\begin{matrix} C_{11} & C_{12} \\ C_{21} & C_{22} \\ \end{matrix} \right] \end{aligned} \]

其中

\[ \begin{bmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{bmatrix} = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} \cdot \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix} \]

矩阵 \(C\) 可以通过下列公式求出：

\[ \begin{aligned} C_{11} = A_{11} \cdot B_{11} + A_{12} \cdot B_{21} \\ C_{12} = A_{11} \cdot B_{12} + A_{22} \cdot B_{21} \\ C_{21} = A_{21} \cdot B_{11} + A_{22} \cdot B_{21} \\ C_{22} = A_{21} \cdot B_{12} + A_{22} \cdot B_{22} \\ \end{aligned} \]

从上述公式我们可以得出，计算 \(2\) 个 \(n \times n\) 的矩阵相乘需要 \(2\) 个 \(\frac{n}{2} \times \frac{n}{2}\) 的矩阵 \(8\) 次乘法和 \(4\) 次加法。

我们使用 \(T(n)\) 表示 \(n \times n\) 矩阵乘法的时间复杂度，那么我们可以根据上面的分解得到下面的递推公式：

\[ T(n) = 8 \times T(\frac{n}{2}) + O(n^{2}) \]

其中：

1. \(8T(\frac{n}{2})\) 表示 \(8\) 次矩阵乘法，而且相乘的矩阵规模降到了 \(\frac{n}{2}\)。
2. \(O(n^{2})\) 表示 \(4\) 次矩阵加法的时间复杂度以及合并矩阵 \(C\) 的时间复杂度。

最终可计算得到 \(T(n)=O(n^{log_{2}^{8}})=O(n^{3})\) 。

可以看出每次递归操作都需要 \(8\) 次矩阵相乘，而这正是瓶颈的来源。相比加法，矩阵乘法是非常慢的，于是我们想到能不能减少矩阵相乘的次数呢？

答案是当然可以！！！

\(\textit{Strassen}\) 算法正是从这个角度出发，实现了降低算法复杂度！

By Long Luo

Leetcode 172. 阶乘后的零 题解：

方法一：用大数暴力求解并计算末尾0的数量

因为 \(n!\) 得到的数字会非常大，所以需要使用BigInteger，得到结果之后，再计算末尾 \(0\) 的数量。

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

import java.math.BigInteger;

class Solution {
    public int trailingZeroes(int n) {
        BigInteger nFactorResult = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            nFactorResult = nFactorResult.multiply(BigInteger.valueOf(i));
        }

        int ans = 0;
        while (nFactorResult.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
            ans++;
            nFactorResult = nFactorResult.divide(BigInteger.TEN);
        }

        return ans;        
    }
}

复杂度分析

• 时间复杂度：\(O(n)\), 实际上应该是 \(O(n + \log n)\)，但 \(\log n\) 很快，只有 \(O(1)\)，所以 \(O(n)\) 。
• 空间复杂度：\(O(1)\)。

方法二：计算1到n中全部5因子数量

思路与算法：

考虑到计算阶乘末尾的每个 \(0\) 表示乘以 \(10\)，那么在我们在计算 \(n!\) 时乘以 \(10\) 的次数是多少？ 考虑到两个数字 \(a\) 和 \(b\) 相乘，例如，要执行 \(15 \times 24 = 360\)，我们可以将其分解为：

\[ 15 \times 24 = 3 \times 5 \times 2 \times 2 \times 2 \times 3 = 360 \]

从上面可以得出，我们只需要考虑 \(2 \times 5\) 的因子有多少对。同时，因为 \(2\) 的因子数比 \(5\) 的因子数要多，所以我们只需要计算 \(1\) 到 \(n\) 的 \(5\) 的因子数有多少即可。

By Long Luo

Leetcode 2. 两数相加 题解。

方法一：模拟链表操作

思路与算法：

最开始我的思路是将 \(2\) 个数字都读出来，然后相加，再逆向写入回去，但是发现链表数字太长，这个方法不可行。

由于两个链表长度不一致，还需要考虑不同位数对齐的问题，但是由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

那么只需要同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 \(n_1\) ，\(n_2\) ，进位值为 \(\textit{carry}\) ，则它们的和为 \(n_1 + n_2 + \textit{carry}\) 。

其中，答案链表处相应位置的数字为 \((n_1 + n_2 + \textit{carry}) mod 10\) ，而新的进位值为 \(\textit{sum} - 10\) 。

需要注意的是：如果链表遍历结束后，有 \(\textit{carry} \gt 0\) ，还需要在答案链表的后面附加一个节点，节点的值为 \(\textit{carry}\) 。

于是就有了那么的第一版代码：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode pNode1 = l1;
	ListNode pNode2 = l2;
	ListNode dummyNode = new ListNode(-1);
	ListNode pNode = dummyNode;
	int carry = 0;
	while (pNode1 != null && pNode2 != null) {
		int sum = pNode1.val + pNode2.val + carry;
		carry = 0;
		if (sum >= 10) {
			sum -= 10;
			carry = 1;
		}
		ListNode node = new ListNode(sum);
		pNode.next = node;
		pNode = pNode.next;

		pNode1 = pNode1.next;
		pNode2 = pNode2.next;
	}

	while (pNode1 != null) {
		int sum = pNode1.val + carry;
		carry = 0;
		if (sum >= 10) {
			sum -= 10;
			carry = 1;
		}
		ListNode node = new ListNode(sum);
		pNode.next = node;
		pNode = pNode.next;

		pNode1 = pNode1.next;
	}

	while (pNode2 != null) {
		int sum = pNode2.val + carry;
		carry = 0;
		if (sum >= 10) {
			sum -= 10;
			carry = 1;
		}
		ListNode node = new ListNode(sum);
		pNode.next = node;
		pNode = pNode.next;
		pNode2 = pNode2.next;
	}

	if (carry > 0) {
		ListNode node = new ListNode(carry);
		pNode.next = node;
	}

	return dummyNode.next;
}

实际上，上述代码可以优化，去掉多余的变量。如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 \(0\) ，得到了下面的优化代码：

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

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode dummyNode = new ListNode(-1);
	ListNode pNode = dummyNode;
	int carry = 0;
	while (l1 != null || l2 != null) {
		int num1 = l1 != null ? l1.val : 0;
		int num2 = l2 != null ? l2.val : 0;
		int sum = num1 + num2 + carry;
		carry = sum / 10;
		pNode.next = new ListNode(sum % 10);
		pNode = pNode.next;

		if (l1 != null) {
			l1 = l1.next;
		}

		if (l2 != null) {
			l2 = l2.next;
		}
	}

	if (carry > 0) {
		pNode.next = new ListNode(carry);
	}

	return dummyNode.next;
}

复杂度分析

• 时间复杂度：\(O(\max(m,n))\) ，其中 \(m\) 和 \(n\) 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 \(O(1)\) 的时间。
• 空间复杂度：\(O(1)\) 。

By Long Luo

1. 两数之和 题解。

方法一：暴力枚举

思路及算法：

最容易想到的方法是使用两层循环，第一层循环枚举数组中的每一个数 \(x\)，下一层循环在 \(x\) 之后的元素中寻找数组中是否存在 \(\textit{target} - x\)。

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

    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

复杂度分析

• 时间复杂度：\(O(N^2)\) ，其中 \(N\) 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
• 空间复杂度：\(O(1)\) 。

1. 褚老师经历过人生最低谷吗？你信命信风水吗？

褚老师经历过人生最低谷吗？你信命信风水吗？未来哪些行业有赚钱机会？

一

我是一个挺迷信的人。

比如我一直坚信好事一旦说出来肯定会泡汤。写了一篇感觉很好的论文，投出去千万别到处说，尤其是不能说「感觉不错，这篇估计要中」之类的话——说要中肯定中不了，不管你理论多牛逼实验多周到结果多惊人文笔多流畅，一定会在你意想不到的地方出漏子。

比如你认识了一个美女，感觉特好约她周末出来吃晚饭，而且她居然答应了。你千万别一高兴就跟同宿舍的哥们儿汇报战果，一旦说了，你瞧着吧，就在礼拜六约好的时间前你一定会收到美女的微信，说哎呀抱歉我有事来不了了咱们以后再约吧。

比如我一直有一个强迫症，在街上走路碰到井盖一定要从井盖上踩过去，有时候就算井盖在马路的中间而马路上有车，我还是会忍不住冒险去踩那个井盖，最糟糕的是如果路上连着有好几个井盖而且位置还忽左忽右，在旁观者眼里我一定看起来像个疯子。

忘了一个细节，我不仅要踩到井盖，而且必须是踩井盖的左半边。如果不是这样，我会觉得很不吉利。

我类似的迷信还有好多，比如做一件重要的大事之前不能理发，比如不能拿自己珍惜的人或东西的名字当密码，比如……

作为一个学物理的「科学工作者」，我当然知道这些绝不是什么理性的举动，当然，更毫无科学依据可言，用你的话说，我的各种迷信纯属——脑残。

可是，我还是不敢把好事提前说出来，我还是会忍不住去踩井盖。

我想说的是，我不信风水，可是我很能理解那些信风水的朋友，以及风水能够给人带来的安慰——生活中不确定的东西太多，而每个人又都渴望得到确定的答案，希望自己能为改变不能改变的命运做点儿什么，如果能踩井盖给自己带来点儿好运气，如果把卧室里的床换个位置就会事业上升走桃花运之类的，我想谁都会有难以拒绝的时候吧。

而且，比起踩井盖来说，风水也许还更靠谱一点。

二

先告诉你一个坏消息吧，你没法说服一个信风水的人。

单从这一点上看，风水这东西很像中医，一个人一旦信了中医，不管你怎么摆事实、讲道理或者采取什么冷招数想说服他都基本没戏。

但是，我想说的是：风水跟中医太不一样了！

鲁迅老师说过：「中医不过是一些有意无意的骗子。」风水师不是什么「有意无意」的骗子，这帮人无一例外都是有意的骗子。

在现代医学出现之前，一个中国人要是生病了，你只有一个选择——看中医。说句公道话，虽然中医癌症心脏病肝炎肺炎还有各种传染病什么的大病小病都治不了，但是你得了感冒让你退个烧出个汗还是可以做到的，所以不能说完全没用。我相信古时候的中医很多还是真心想给病人治病的，问题不是缺德，而是无知。

现代的中医则是另外一回事。前一段一个傻逼中医假装提问想跟我叫板，我写了一篇长文讲解了中医的问题，有空你看看吧，我就不在这儿重复了。

简单说吧，现代的中医都缺德。

中医属于那种过去有过用，后来被更有用的替代了的东西。而风水则不同，风水属于那种以前就没用，现在也没用，以后也不会有用的彻头彻尾的骗局。

风水师都是骗子，但是——他们没中医那么缺德。

因为风水不杀人。

风水造成的损失顶多像你问题里说的，买坟地的时候花点儿冤枉钱之类的，除了让一些弱智自愿破财以外对当事人基本无害，作为一种智商罚款，我觉得对社会总的来说还有好处。

从更深一层看，风水师提供的其实是一种有极大市场需求的服务。你说风水师是卖什么的？卖「风水」的？错！

风水师是卖「希望」的。

你想职场得意、生意发达、家庭幸福、孩子上名校，哪件事不都是需要费了大劲才能实现的？现在有人跟你说，有一个简单的解决方案——你只需要把家里的家具重新摆一摆就万事大吉了——这得多有吸引力啊！要是真有这样的好事，我也会马上掏腰包。

从这个角度来看，风水师跟网上那些卖「财富自由、年薪百万」秘籍的所谓「知识付费」骗子其实没什么差别，套路都是说只要你花点儿钱，就能迎来人生转折，梦想成真。

再往深一层看，风水师其实比卖「财富自由」的还要高明一些，那些成功秘籍骗了你的钱之后还是让你自己去努力去瞎费劲。但是你知道吗，决定成功的最大因素是机遇——是那些偶然的、不受你控制的东西。

我想其实每个人心里都隐隐地感到了这一点，所以才会去为风水、烧香这样的虚幻的东西付费。像你说的，越是成功的明星、商人就越容易信风水，因为这类人最清楚，自己的成功来得莫名其妙。

风水存在的根本原因，就是成功主要靠运气这个真理。牛逼！

中医骗了你的钱把你害死，卖财富自由的骗了你的钱让你瞎忙，只有风水师，骗了你的钱就基本没事儿了。

还是风水好哇！