首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

关于O(f(n))表示的有关问题

2013-01-17 
关于O(f(n))表示的问题书上对O符号表达的的定义O(f (n)) {g(n) : there exists c 0, and n0 such that

关于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)的。

热点排行