(渐进记号的性质)假设f(n)和g(n)为渐近正函数。证明或反驳下面的每个猜测。
a. f(n)=O(g(n))蕴含g(n)=O(f(n))。
b. f(n)+g(n)=θ(min(f(n), g(n))。
c. f(n)=O(g(n))蕴含lg(f(n))=O(lg(g(n))),其中对所有足够大的n,有且。
d. f(n)=O(g(n))蕴含。
e. f(n)=。
f. f(n)=O(g(n))蕴含g(n)=Ω(f(n))。
g. f(n)=。
h. f(n)+o(f(n))=。
解答:
a. f(n)=O(g(n))蕴含g(n)=O(f(n))。 错误。
举例 , 。
b. f(n)+g(n)=θ(min(f(n), g(n))。错误。
举例,,
c. f(n)=O(g(n))蕴含lg(f(n))=O(lg(g(n))),其中对所有足够大的n,有且。正确。
根据O定义:
O(g(n)) = { f(n): 存在正常量c和,使得对所有,有 }
由不等式可得
。
d. f(n)=O(g(n))蕴含。正确。
根据O定义:
O(g(n)) = { f(n): 存在正常量c和,使得对所有,有 }
由不等式可得
e. f(n)=。错误。
举反例,取,则。已知n>0时,。所以命题e不成立。
f. f(n)=O(g(n))蕴含g(n)=Ω(f(n))。
从O的定义来分析该问题,O定义如下:
O(g(n)) = { f(n): 存在正常量c和,使得对所有,有 }
Ω(g(n)) = { f(n): 存在正常量c和,使得对所有,有 }
g. f(n)=。错误。
举反例。取,则,由于,所以命题不成立。
h. f(n)+o(f(n))=。正确。
根据o的定义,我们可以得到
存在正常量c和,使得对于所有,有,
另外,由于,可得 。
因此我们可以得到
,因此符合θ函数的定义。故命题成立。