题目
以下关于渐进记号的性质是正确的有:( )A. f(n) =Θ(g(n)),g(n) =Θ(h(n)) ⇒f(n) =Θ(h(n))B. f(n) =O(g(n)),g(n) =O(h(n)) ⇒h(n) =O(f(n))C. O(f(n))+O(g(n)) = O(min(f(n),g(n)))D. f(n) = O(g(n)) ⇔g(n) = O(f(n))
以下关于渐进记号的性质是正确的有:( )
A. f(n) =Θ(g(n)),g(n) =Θ(h(n)) ⇒f(n) =Θ(h(n))
B. f(n) =O(g(n)),g(n) =O(h(n)) ⇒h(n) =O(f(n))
C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})
D. f(n) = O(g(n)) ⇔g(n) = O(f(n))
题目解答
答案
A. f(n) =Θ(g(n)),g(n) =Θ(h(n)) ⇒f(n) =Θ(h(n))
解析
渐进记号(如O、Ω、Θ)用于描述算法时间复杂度的增长速率关系。本题考查对这些符号传递性、结合性及运算性质的理解。关键点在于:
- Θ符号的传递性:若$f(n)=Θ(g(n))$且$g(n)=Θ(h(n))$,则$f(n)=Θ(h(n))$;
- O符号的非对称性:若$f(n)=O(g(n))$且$g(n)=O(h(n))$,不能推出$h(n)=O(f(n))$;
- 渐进阶的加法性质:$O(f(n)) + O(g(n))$的阶由较大项决定,而非较小项;
- O与Θ的关系:$f(n)=O(g(n))$不等价于$g(n)=O(f(n))$,除非两者为Θ关系。
选项A
正确。
若$f(n)=Θ(g(n))$,则存在常数$c_1,c_2>0$和$n_0$,使得$c_1g(n) \leq f(n) \leq c_2g(n)$对所有$n \geq n_0$成立。同理,$g(n)=Θ(h(n))$可推出$g(n)$与$h(n)$的类似不等式。将两者结合,可推导出$f(n)$与$h(n)$满足Θ关系,即$f(n)=Θ(h(n))$。Θ符号具有传递性。
选项B
错误。
假设$f(n)=n$,$g(n)=n^2$,$h(n)=n^3$,则$f(n)=O(g(n))$,$g(n)=O(h(n))$,但$h(n)=n^3$显然不是$O(f(n)=n)$。O符号的传递性不保证反向包含。
选项C
错误。
例如,$f(n)=n$,$g(n)=n^2$,则$O(f(n)) + O(g(n)) = O(n^2)$,而$\min\{f(n),g(n)\}=n$,等式右边为$O(n)$,显然不成立。渐进阶的和由较大项决定。
选项D
错误。
若$f(n)=n$,$g(n)=n^2$,则$f(n)=O(g(n))$,但$g(n)$不是$O(f(n))$。O符号单向成立不代表双向等价,除非两者为Θ关系。