关于O(f(n))表示的问题
书上对O符号表达的的定义
O(f (n)) = {g(n) : there exists c > 0, and n0 such that g(n)<=c*f(n) for all n>=n0}
书上还给了一个例子:
若T (n) = a + b(n + 1) + cn + dn + en
则T(n)=O(n)
但我觉得根据O符号表达的定义,应该是T(n)=O(n)+C (C为常数,即C=a+b)
[解决办法]
常数会被O(n)吃掉。
你如果g(n)<=c*n对n>=n0成立的话,那g(n)+C<=(c+C)*n,对n>=max(1,n0)成立。
所以g(n)+C也是O(n)的。