大O表示法定义： $$ 当 x > k 时，|f(x)|<=C|g(x)|，C|g(x)｜就记做\ O(g(x)) $$ 这个其实很简单，分为2个部分取考虑：
f(x)是什么，即代码会执行多少次。
例1：
// $n=100;
for($i=1;$i<=$n;$i++){
print "当前i的值是：".$i.PHP_EOL;
}问，上面这个函数执行多少次？答：1+3*n。$i=1是1，$i<=$n，$i++，print print "当前i的值是：".$i.PHP_EOL;各会执行n次，所以总次数为1+3*n次，即f(x)=1+3*n。
然后考虑，当n趋紧于无限大的时候，+1和*3对n的值影响到不大，所以大O表示法就可以写成
$$
f(x)=1+3x=O(x) \
或者用更加习惯的n来替代x \
O(n)
$$
例2:
for($i=1;$i<=$n;$i++){
for($j=1;$j<=$n;$j++){
print "当前i和j的值为:({$i},{$j})".PHP_EOL;
}
}例2中，函数执行了多少次？n*(3*n+1)+2*n+1，计算后得到结果：
$$
3{n}^{2}+3n+1
$$
然后我们设想，n的平方的增加速度会比3n快很多，当n趋近于无限大的时候，上面的函数起主要作用的就是n的平方。
$$
f(x)=3{n}^{2}+3n+1=O({n}^{2})
$$
上面这两个例子可以总结成下面的这个定理：
$$
f(x)={a}{n}{x}^{n}+{a}{n-1}{x}^{n-1}+{a}{n-2}{x}^{n-2} \cdots + {a}{1}{x}^{1}+ {a}{0}{x}^{0} \
{a}{n} \in Q，\
f(x)=Q({x}^{n})
$$
证明过程：
$$
x>=1时\
|f(x)|=|{a}{n}{x}^{n}+{a}{n-1}{x}^{n-1}+{a}{n-2}{x}^{n-2} \cdots + {a}{1}{x}^{1}+ {a}{0}{x}^{0}| \
<=|{a}{n}|{x}^{n}+|{a}{n-1}|{x}^{n-1}+|{a}{n-2}|{x}^{n-2} \cdots + |{a}{1}|{x}^{1}+ |{a}{0}|{x}^{0} \
= {x}^{n}({a}{n}+{a}{n-1} \times \frac{1}{x} +{a}{n-2} \times \frac{1}{{x}^{2}} \cdots +{a}{1} \times \frac{1}{{x}^{n-1}} +{a}{n} \times \frac{1}{{x}^{n}}) \
<= {x}^{n}({a}{n}+{a}{n-1}+{a}{n-2} \cdots {a}{1}+{a}{0}) \
即 |f(x)|<=C|g(x)|，g(x)={x}^{n}，即 f(x)=O({x}^{n})
$$
至于这里为什么要x>1，是因为执行步骤肯定是存在的，如果没有执行步骤，那么讨论算法复杂度就没有意义了。
相加： $$ 如果，{f}{1}=O({g}{1}(x)),{f}{2}=O({g}{2}(x)),\则({f}{1}+{f}{2})(x)=O(g(x))，g(x)=max({g}{1}(x),{g}{2}(x)) $$ 相乘： $$ 如果，{f}{1}=O({g}{1}(x)),{f}{2}=O({g}{2}(x)),\则({f}{1}{f}{2})(x)=O(g(x))，g(x)=({g}{1}(x){g}{2}(x)) $$
上面是考虑x趋于无限大，这里则不是，具体根据定义来推倒吧，或者可以说是算法的一般情况。