Big O notation

趁着空闲下来，准备补一下计算机基础知识。

算法一直是想学习又觉得比较困难的事物，每每觉得数学基础不好，不清楚这些算法底下的数学含义之类的。但现在又觉得，数学作为 CS 的一门基础课程，先会使用再去理解（也不用像学数学的那样去理解）应该才是更好的。

说到算法，一般都会提到 Big O 这个概念，它作为算法复杂度分析的必要要素，了解它应该是最优先的。

按照 Wikipedia 的解释，在 CS 中，Big O 是用来分类算法的，根据算法对于 input size 的变化而作出的反应来进行分类。所以会有下列几种类别：

1. O(1)
2. O(n)
3. O(log n)

等等。

如果知道上述几个表达式的意义，那么我们就知道这些是用来表示，当 input size ，也就是 n 不断变化时，运行这段程序所需要的时间是如何变化的。

比如说我们有个表达式： 5n + 3

那么计算这一表达式，随着 n 的不断增加，它的计算时间的变化我们知道会是 O(n)，但是这是如何得出来的，那么就需要引入 Big O 概念的数学表达式：

当然这个表达式看的我也是只知道它在说什么而已，Youtube 上的这个讲解视频 Big O Notation (and Omega and Theta) — best mathematical explanation (video) 才很清晰的说明了这个表达式的意思，按照视频所说：

Big O 的意思既是当 x > x1 时， f(x) 永远小于或等于 Cg(x)，C 为一个常数。那么 g(x) 就是 O 括号里的表达式，推荐看视频，在不同的情况下，我们可以得出很多种 g(x) ，但是只取最接近状态的 g(x) ，就是说满足上述条件的最简形式（最小值？）。比如说 n, 2n, 3n 作为 g(x)，都可以满足当 x 大于某个数值时，5x + 3 ≤ g(x)，但是 n 是满足这个条件最简单的形式，那么 5n + 3 的时间复杂度就由 O(n) 来表示了。

由 Big O, Omega, Theta 组合起来的概念就可以在不需要对算法进行实际的运行测试，而直接在抽象的层面上来得出算法的复杂度。