如果f(n) = O(g(n))且g(n) = O(f(n))那么是什么情况呢？
g(n)和f(n)的增长速度相同。
由 f(n) = O(g(n)) 可以得到f(n)的增长速度小于等于g(n)
由 g(n) = O(f(n)) 可以得到g(n)的增长速度小于等于f(n)
那么，两个函数的增长速度相同
f(n) = g(n) ？
当然不必相等。
因为大O记号是一种小于等于关系，忽略的系数和低位项。
很容易举一个反例：
1 | f(n)=n |
f(n)/g(n)的极限一定存在吗？
直观的讲， f(n) = O(g(n)) 推出 f(n) ≤ cg(n) ， g(n) = O(f(n))推出 g(n) ≤ kf(n)
得到 mg(n) ≤ f(n) ≤ cg(n) ，这里的m = 1/k
也就是说 f(n) = Θ(g(n))
这时， f(n)/g(n) 得极限是一个非零的常数
但是极限一定存在吗?
我们可以构造两个函数满足题意但是极限又不存在
1 | f(n)=1 |
令c = 1，k = 3，使得对于n>1的所有情况，都满足大O定义
但是两者的比值 f(n)/g(n) = 1/(2+cos(n)) ，极限是不存在的，在[1/3,1]之间波动，无法稳定的趋于某个定值。