题目
以下关于渐进记号的性质是正确的有:( )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))
解析
步骤 1:理解渐进记号的定义
渐进记号用于描述算法的运行时间或空间复杂度。Θ记号表示一个函数的上界和下界,O记号表示一个函数的上界,而Ω记号表示一个函数的下界。如果f(n) = Θ(g(n)),则存在正常数c1、c2和n0,使得对于所有n ≥ n0,有c1g(n) ≤ f(n) ≤ c2g(n)。如果f(n) = O(g(n)),则存在正常数c和n0,使得对于所有n ≥ n0,有f(n) ≤ cg(n)。
步骤 2:分析选项A
f(n) = Θ(g(n)),g(n) = Θ(h(n)),则存在正常数c1、c2、c3、c4和n0,使得对于所有n ≥ n0,有c1g(n) ≤ f(n) ≤ c2g(n)和c3h(n) ≤ g(n) ≤ c4h(n)。因此,c1c3h(n) ≤ f(n) ≤ c2c4h(n),即f(n) = Θ(h(n))。所以选项A正确。
步骤 3:分析选项B
f(n) = O(g(n)),g(n) = O(h(n)),则存在正常数c1、c2和n0,使得对于所有n ≥ n0,有f(n) ≤ c1g(n)和g(n) ≤ c2h(n)。因此,f(n) ≤ c1c2h(n),即f(n) = O(h(n))。但不能推出h(n) = O(f(n))。所以选项B错误。
步骤 4:分析选项C
O(f(n)) + O(g(n)) = O(max{f(n), g(n)}),而不是O(min{f(n), g(n)})。所以选项C错误。
步骤 5:分析选项D
f(n) = O(g(n)),则存在正常数c和n0,使得对于所有n ≥ n0,有f(n) ≤ cg(n)。但不能推出g(n) = O(f(n))。所以选项D错误。
渐进记号用于描述算法的运行时间或空间复杂度。Θ记号表示一个函数的上界和下界,O记号表示一个函数的上界,而Ω记号表示一个函数的下界。如果f(n) = Θ(g(n)),则存在正常数c1、c2和n0,使得对于所有n ≥ n0,有c1g(n) ≤ f(n) ≤ c2g(n)。如果f(n) = O(g(n)),则存在正常数c和n0,使得对于所有n ≥ n0,有f(n) ≤ cg(n)。
步骤 2:分析选项A
f(n) = Θ(g(n)),g(n) = Θ(h(n)),则存在正常数c1、c2、c3、c4和n0,使得对于所有n ≥ n0,有c1g(n) ≤ f(n) ≤ c2g(n)和c3h(n) ≤ g(n) ≤ c4h(n)。因此,c1c3h(n) ≤ f(n) ≤ c2c4h(n),即f(n) = Θ(h(n))。所以选项A正确。
步骤 3:分析选项B
f(n) = O(g(n)),g(n) = O(h(n)),则存在正常数c1、c2和n0,使得对于所有n ≥ n0,有f(n) ≤ c1g(n)和g(n) ≤ c2h(n)。因此,f(n) ≤ c1c2h(n),即f(n) = O(h(n))。但不能推出h(n) = O(f(n))。所以选项B错误。
步骤 4:分析选项C
O(f(n)) + O(g(n)) = O(max{f(n), g(n)}),而不是O(min{f(n), g(n)})。所以选项C错误。
步骤 5:分析选项D
f(n) = O(g(n)),则存在正常数c和n0,使得对于所有n ≥ n0,有f(n) ≤ cg(n)。但不能推出g(n) = O(f(n))。所以选项D错误。