算法基础-函数渐近
渐近等价
考虑函数: f(x)=x²+4x
当x→∞时，该函数可以看作x平方与它的高阶无穷小o(x²)之和，即
于是我们称f(x)和x²是渐近等价的。用符号表示为
更一般地，如果存在两个函数f(x)和g(x)，使得
你也可以用极限的方法来判断两个函数是否渐近等价
我们可以轻而易举地得到一个结论：f(x)总是跟自己渐近等价
渐近上界
若对于函数 f(n)，g(n)，存在c和k，使得
即从k开始，f(n)永远无法超过cg(n)，则称g(n)为f(n)的渐近上界，写作
注意O(g(n))表示的是一个集合，它代表了所有以g(n)为渐近上界的函数，此处的等于号是用于指出f(n)是所有以g(n)为渐近上界的函数里的一元
下面的图片可以帮助你更好的理解f(n)与g(n)的关系
若选取 c=5 ，则当x>1时，f(n)<5g(n)
同样的，我们也可以轻易得到一个结论，f(x)总是自己的渐近上界
渐近时间复杂度
设有下面一段函数
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
swap(i,j);
}
}外循环共执行了n次，内循环共执行了i次，所以总共执行次数为
如果我们把代码改成如下所示
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
execute1(i,j);
execute2(i,j);
execute3(i,j);
execute4(i,j);
}
}那么此时算法执行命令的总次数就翻了4倍
随着n的逐渐增大，这两个算法所用时间的增长规模是相似的，并且我们并不需要特别高的精度
因此我们可以用算法执行时间 t(n) 的渐近上界 f(n) 来表示一个算法的效率
在渐近时间复杂度中，我们只关心执行时间的增长规模，而不关心具体数字，显然以下两个函数的规模是一致的
因此我们需要对渐近时间复杂度进行化简
函数推导
f(n)=O(g(n))Λg(n)=O(h(n))→f(n)=O(h(n))
根据定义，我们得到
合并，得到
命题得证
f(x)~g(x)→O(f(x))=O(g(x))
我们设 h(x) = O(f(x))，由渐近等价得定义得
由无穷小定义可得，对于任意 ε>0，总存在N，使得下列不等式成立
取 ε=1，便得到
替换掉f(x)，得到
命题得证
其它结论
通过上面两个结论，再利用其它高等数学知识，我们便可以推出下面的结论
因此，在计算渐近时间复杂度时，若出现多项式，我们可以遵守以下准则
- 只保留最高阶的项
- 最高阶的项系数为1
例如: O(4n³+2n²+9)=O(n³)