算法复杂度有五种表示方法 \(\mathcal{O}\), \(\Theta\), \(\Omega\), \(\mathcal{o}\), \(\omega\)
1. \(\mathcal{O}\text{-notation}\)
\(\mathcal{O}\)表示法读作big oh notation, 中文为大O表示法，表示算法复杂度时常用的一种表示方法，定义为 \[ O(g(n)) = \{ f(n):\text{there exist positive constants } c \text{ and } n_0 \text{ such that } \\ 0 \le f(n) \le cg(n) \text{ for all } n \geq n_0 \} \] 它所表示的是上限约束，用图像可以表示为
下面举一个简单的例子说明一下
int sumVector(vector<int>& v){
int s = 0, sz = v.size();
for(int i = 0; i < sz; i++){
s += v[i];
}
return s;
}这个函数是将vector中所有元素相加然后返回，里面仅有一个遍历数组v的循环，所以随着数组的大小最大运行时间应该呈线性增大，所以可以说它的算法复杂度用\(\mathcal{O}\)表示法可以表示为\(T_{n} \in \mathcal{O}(n)\)，因为\(\mathcal{O}(n)\)表示的是一个集合所以这里用的是属于符号，也有很多人使用等于号不过这里等于号表示的并不是“等于”的意思而是表示的“是”。
2. \(\Theta\text{-notation}\)
\(\Theta\)表示法的定义为 \[ \Theta(g(n)) = \{f(n): \text{there exist positive constants }c_1 \text{, }c_2\text{, and }n_0\text{ such that }\\ 0 \leq c_1g(n) \leq f(n) \leq c_2g(n) \text{ for all } n \geq n_0 \} \] 所以它同时表示上限与下限约束，用图像可以表示为
还是以上面那个数组求和为例，它的算法复杂度用\(\Theta\)表示法可以表示为\(T_{(n)} = \Theta(n)\)。
3. \(\mathcal{\Omega}\text{-notation}\)
\(\Omega\)表示法的定义为 \[ \Omega(g(n)) = \{ f(n): \text{there exist positive constants } c \text{ and }n_0 \text{ such that} \\ 0 \leq cg(n) \leq f(n) \text{ for all } n \geq n_0 \} \] \(\Omega\)与\(\mathcal{O}\)相对应表示的是下限约束，用图像可以表示为
4. \(\mathcal{o}\text{-notation}\)
\(\mathcal{o}\text{-notation}\)读作litter oh notation，中文是小o表示法，它的定义可以表示为 \[ o(g(n)) = \{ f(n)\text{ : for any positive constant } c >0 \text{ , there exists a constant } \\ n_0 > 0 \text{ such that } 0 \leq f(n) < cg(n) \text{ for all } n \geq n_0 \} \] 和\(\mathcal{O}\)一样都是表示上限约束，不过在\(\mathcal{O}\)表示法的定义中是存在一个\(c > 0\)即可成立而此处则是对于任意\(c > 0\)都得成立，举个例子\(2n^2 = \mathcal{O}{(n^2)}\)，但是\(2n^2 \neq \mathcal{o}{(n^2)}\)。
5. \(\omega\text{-notation}\)
\(\omega\)的定义为 \[ \omega(g(n)) = \{ f(n) : \text{for any positive consant } c > 0 \text{, there exists a constant} \\ n_0 > 0 \text{ such that } 0 \leq cg(n) < f(n) \text{ for all } n \geq n_0 \} \] 和\(\mathcal{\Omega}\)表示法一样都表示下限约束，在\(\mathcal{\Omega}\)表示法中是存在一个\(c > 0\)即可成立而此处则是对于任意\(c > 0\)都成立。