Math

先用几句话简单说明一下时间复杂度。**时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序运行需要的时间增长得有多快。**也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是一样的，我们就说这个程序很好，具有 $O(1)$ 的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是 $O(n)$，比如找 $n$ 个数中的最大值；而像冒泡排序、插入排序等，数据扩大 $2$ 倍，时间变慢 $4$ 倍的，属于 $O(n^2)$ 的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是 $O(a^n)$ 的指数级复杂度，甚至 $O(n!)$ 的阶乘级复杂度。不会存在 $O(2n^2)$ 的复杂度，因为前面的那个 $2$ 是系数，根本不会影响到整个程序的时间增长。同样地，$O (n^3+n^2)$ 的复杂度也就是 $O(n^3)$ 的复杂度。因此，我们会说，一个 $O(0.01n^3)$ 的程序的效率比 $O(100n^2)$ 的效率低，尽管在 $n$ 很小的时候，前者优于后者，但后者运行所需的时间随数据规模增长得慢，最终 $O(n^3)$ 的复杂度将远远超过 $O(n^2)$。我们也说，$O(n^{100})$ 的复杂度小于 $O(1.01^n)$ 的复杂度。 ...

按照定义，方差的 estimator 应该是： $$ \begin{equation} S^2 = \frac{1}{n}\sum_{i = 1}^n\left(X_i - \overline{X}\right)^2 \label{eq:sample-variance} \end{equation} $$ 但是这个 estimator 有 bias，因为： $$ \begin{align*} E(S^2) &= \frac{1}{n}\sum_{i = 1}^nE\left[\left(X_i - \overline{X}\right)^2\right] \\ &= \frac{1}{n}E\left[\sum_{i = 1}^n\left(X_i - \mu + \mu - \overline{X}\right)^2\right]\\ &= \frac{1}{n}E\left[\sum_{i = 1}^n\left(X_i - \mu\right)^2 - n \left(\overline{X} - \mu \right)^2\right] \\ &= \frac{1}{n} \left[\sum_{i = 1}^nE\left(\left(X_i - \mu\right)^2\right) - nE\left(\left(\overline{X} - \mu\right)^2\right)\right] \\ &= \frac{1}{n}\left[n\operatorname{Var}(X) - n\operatorname{Var}(\overline{X})\right] \\ &= \operatorname{Var}(X) - \operatorname{Var}(\overline{X}) \\ &= \sigma^2 - \frac{\sigma^2}{n} = \frac{n - 1}{n}\sigma^2 \end{align*} $$ 关于 $\operatorname{Var}(\overline{X}) = \frac{\sigma^2}{n}$ 的证明参考： Prove that $E (\overline{X} - \mu)^2 = \frac{1}{n}\sigma^2$ ...

公约数和最大公约数 公约数 在这里，我们约定集合 $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$ 表示所有的整数，集合 $\mathbb{N} = \{0, 1, 2, \dots\}$ 表示所有的自然数。 对于任意的实数 $x$，将小于等于 $x$ 的最大整数记作 $\lfloor x \rfloor$，读作 “the floor of $x$”。对于任意的整数 $a$ 和任意正整数 $n$，$a \operatorname{mod} n$ 表示 $a / n$ 的余数（remainder or residue），也就是说： ...

接触的契机 Cauchy-Schwarz不等式是一个很有名的不等式，多次在不同的地方遇见。当我读 Introduction to Linear Optimization 时再次遇见它却不知道如何证明，于是写下此文用于记录各种证明方法以供查阅，本文参考了台湾阳明交通大学应用数学系教授 林琦焜的《Cauchy-Schwarz不等式之本質與意義》论文。 ...

在我读一篇关于 基于机器学习的无人机路线规划问题的论文时，文章中提出了一个检测无人机行驶的路线中如果遇到受限制的区域（比如禁飞区、军事基地等）应该如何绕行的问题，其中就需要先检测飞行的路线是否经过受限制的区域的问题，在这里我们可以将这个问题简化成： ...

注：关于参考文献的格式可以参考 清华大学的研究帮助，本文没有严格按照参考文献的格式引用。 机器学习和数据挖掘 P、NP、NPC和NP-Hard是什么，以及它们之间的关系： ...