大 O、大 Omega、大 Theta 记号的笔记

定义 0：函数的“家族”。函数 f(x) 的“家族”指的是一个由函数构成的集合：{F(x) | F(x) = cf(x), c>0}。

例子 0.1：x 的家族。令函数 f(x) = x。则 f 的家族就是集合{cx | c >0}。函数 x、2x、1.5 x 都是这个集合的成员。

例子 0.2：f(x) = x^2 的家族。{…, 0.1x^2, …, 0.2x^2, …, x^2, …, 2x^2, …, 10000x^2, …}。我们可以知道，这个家族里的所有成员，最终都会比 y(x) = x 要大（飞得高）。所谓的“最终”，指的是存在一个X，使得过了这个 X 以后，f 的值总会大于y 的值。

定义 1：Big-O 记号。如果存在 c > 0, N > 0， 使得对于任意的 n > N 都有 f(n) <= c g(n)，则称 f(n) is O(g(n))，或直接 f is O(g)。

笔记：用“家族”的概念来解释。如果 g 的家族里有人（大佬）最终能够大过 f，则称 f(n) is O(g(n))。“f 飞不过 g 家大佬。”

例子 1.1：按定义证明 2n + 1 is O(n)。取 c = 3，N = 1，则对任意的 n > 1，都有 2n+1 < 3n。证毕。

笔记：按定义证明 f is O(g) 的格式。按定义证明 f is O(g)，本质上就是证明 c 和 N 存在。证明一个数存在的最简单粗暴的方法就是直接把这个数字找出来。格式就是：取 c = xxx，N = xxx，则对任意的……都有……，证毕。

笔记：用“家族”的概念来理解这个例子。2n+1 飞不过 n 家族的大佬，比如3n、4n 之类的。

例子 1.2：按定义证明 2n + 1 is O(n^2)。取 c = 1，N = 1+ sqrt(2)，则对任意的 n > 1+sqrt(2) 都有 2n+1 < n^2。证毕。

例子 1.3：按定义证明 n^2 is not O(n)。证明之前我们可以先画个图。

(图挂了)

可以看到，n^2（就是图中的 x^2）很强，飞的很高，能把 n 家族里的所有成员都甩开。也就是说“n^2 飞得过 n 家族的大佬。”所以我们可以猜到，n^2 is not O(n)。但是这只是解释而不是证明。接下来就让我们来严格地证明吧。

用反证法（Proof by Contradition）。假设存在 c > 0, N > 0 使得对任意 n > N 都有 n^2 <= cn，即 n <= c。那么，这个 c 便 是集合 {N+1, N+2, ... } 的上界。如果 c 是这个集合的上界，那么，容易看出，c 也是全体自然数集的上界——荒谬！自然数集怎么可能有上界呢？换言之，这个结论与自然数集的性质冲突了。冲突出现，假设不成立，故得证。

笔记：放心，按定义证明 f is not O(g) 这种题一般不会考。就算考了，把那个图画出来，肯定也能拿不少分。所以上面那个反证法看不懂也没关系。

引理 1.4：传递性。若 f is O(g)，g is O(h)，则 f is O(h)。

证明待补完。

引理 1.5：f is O(c f)，其中 c > 0，为常数。

证明。取 k = 1/c，N = 随便一个正数，则对任意的 n 都有 f(n) >= f(n)。证毕。

推论 1.6：c f is O(f)。

定理 1.7：如果 g is O(f)，那么对任意大于零的常数 c，都有 g is O(c f)。

由以上两个引理可证。

定理 1.8：f(n) + g(n) is O(max{f(n), g(n)})。

证明待补完。

例子 1.9：(n + log n)(n + 8) is O(n^2)。

定义 2：Big-Omega 记号。如果存在 c > 0, N > 0， 使得对于任意的 n > N 都有 f(n) >= c g(n)，则称 f(n) is Ω(g(n))，或直接 f is Ω(g)。

笔记：按“家族”概念理解。f 飞得过 g 家萌新。

例子、定理待补完。

定义 3：Big-Theta 记号。如果 f is O(g) 且 f is Omega(g)，则称 f is Theta(g)。

笔记：按“家族”概念理解。f 飞不过 g 家大佬，但 f 还是可以欺负一下 g 家萌新的。换言之，f 被 g 家的大佬和萌新夹在中间。

例子定理待补完。