算法导论 3-4 证明与反驳

(渐进记号的性质)假设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,有算法导论 3-4 证明与反驳算法导论 3-4 证明与反驳

d. f(n)=O(g(n))蕴含算法导论 3-4 证明与反驳

e. f(n)=算法导论 3-4 证明与反驳

f. f(n)=O(g(n))蕴含g(n)=Ω(f(n))。

g. f(n)=算法导论 3-4 证明与反驳

h. f(n)+o(f(n))=算法导论 3-4 证明与反驳

 

解答:

a. f(n)=O(g(n))蕴含g(n)=O(f(n))。 错误。

举例 算法导论 3-4 证明与反驳算法导论 3-4 证明与反驳 。

b. f(n)+g(n)=θ(min(f(n), g(n))。错误。

举例算法导论 3-4 证明与反驳算法导论 3-4 证明与反驳算法导论 3-4 证明与反驳

c. f(n)=O(g(n))蕴含lg(f(n))=O(lg(g(n))),其中对所有足够大的n,有算法导论 3-4 证明与反驳算法导论 3-4 证明与反驳。正确。

根据O定义:

O(g(n)) = { f(n): 存在正常量c和算法导论 3-4 证明与反驳,使得对所有算法导论 3-4 证明与反驳,有算法导论 3-4 证明与反驳 }

由不等式算法导论 3-4 证明与反驳可得

算法导论 3-4 证明与反驳

d. f(n)=O(g(n))蕴含算法导论 3-4 证明与反驳。正确。

根据O定义:

O(g(n)) = { f(n): 存在正常量c和算法导论 3-4 证明与反驳,使得对所有算法导论 3-4 证明与反驳,有算法导论 3-4 证明与反驳 }

由不等式算法导论 3-4 证明与反驳可得

算法导论 3-4 证明与反驳

e. f(n)=算法导论 3-4 证明与反驳。错误。

举反例,取算法导论 3-4 证明与反驳,则算法导论 3-4 证明与反驳。已知n>0时,算法导论 3-4 证明与反驳。所以命题e不成立。

f. f(n)=O(g(n))蕴含g(n)=Ω(f(n))。

从O的定义来分析该问题,O定义如下:

O(g(n)) = { f(n): 存在正常量c和算法导论 3-4 证明与反驳,使得对所有算法导论 3-4 证明与反驳,有算法导论 3-4 证明与反驳 }

Ω(g(n)) = { f(n): 存在正常量c和算法导论 3-4 证明与反驳,使得对所有算法导论 3-4 证明与反驳,有算法导论 3-4 证明与反驳 }

g. f(n)=算法导论 3-4 证明与反驳。错误。

举反例。取算法导论 3-4 证明与反驳,则算法导论 3-4 证明与反驳,由于算法导论 3-4 证明与反驳,所以命题不成立。

h. f(n)+o(f(n))=算法导论 3-4 证明与反驳。正确。

 

 

根据o的定义,我们可以得到

存在正常量c和算法导论 3-4 证明与反驳,使得对于所有算法导论 3-4 证明与反驳,有算法导论 3-4 证明与反驳

另外,由于算法导论 3-4 证明与反驳,可得算法导论 3-4 证明与反驳 。

因此我们可以得到

算法导论 3-4 证明与反驳,因此符合θ函数的定义。故命题成立。

 

 

 

 

 

上一篇:LG-Java工程师高薪训练营【完结】


下一篇:算法导论2-3