Question

大O表示法的计算过程

今天学了下大O算法 但是不是很明白 是一些计算的式子不是程序
说是f(n)=O(g(n)) 当且仅当存在正值常数c和n0,使得对所有n>=n0,有f(n)<=c*g(n).
例如:
1. 5n+4=O(n), 因为对所有n>=4, 5n+4<=6n
2. 6*2^n+n^2=O(2^n),因为对所有n>=4, 6*2^n+n^2<=7*2^n
3. 3n+2不等于O(1),因为不存在正值常数c和n0,使得对所有n>=n0,3n+2<=c

里面的c和n0是怎么算出来的? 而1和3差不多 那为什么两个的原因却不同?
请教下大侠们~ 谢谢 ~~

Answer 1

1和3本来就一样么..居然还有这么恶心的公式..
c和n0是随便找的,只要能找到就行
最简单的判断复杂度的方法就是:对于任何表达式,先合并同类项,然后取含n的最高阶的项,去掉常数
比如2中,n的最高阶的项就是6*2^n,去掉常数就是2^n
一般地,排序算法最快是O(nlog2(n)),折半查找是O(log2(n))

Answer 2

1和3本来就一样么..居然还有这么恶心的公式..
c和n0是随便找的,只要能找到就行
最简单的判断复杂度的方法就是:对于任何表达式,先合并同类项,然后取含n的最高阶的项,去掉常数
比如2中,n的最高阶的项就是6*2^n,去掉常数就是2^n
一般地,排序算法最快是O(nlog2(n)),折半查找是O(log2(n))

Answer 3

莪乜吥倁檤

Answer 4

8