面试问题

Question

这是一个面试问题:

Given: f(n) = O(n)
       g(n) = O(n²)
find f(n) + g(n) and f(n)?g(n)?

这个问题的答案是什么？

Answer 1

当准备这个答案时,f(n)显示为o(n),g(n)显示为Θ(n 2).

从f(n)= o(n)和g(n)=Θ(n²)得到f(n)+ g(n)的o(n²)的下界,但是没有上限在f(n)+ g(n)上,因为没有给出f(n)的上界.[注意,在上面,Θ是一个大θ,或大θ]

对于f(n)·g(n),得到o(n³)的下界,因为Θ(n²)表示g(n)的o(n²)和O(n²)的下限和上限.同样,没有f(n)·g(n)的上界可用,因为f(n)可以任意大; 对于f(n),我们只有一个o(n)下界.

修改问题只给出f和g的上界,如f(n)= O(n)和g(n)= O(n²),我们得到f(n)+ g(n)是O( n 2)和f(n)·g(n)是O(n³).

严格地说明这一点有点单调乏味,但非常简单.例如,对于f(n)·g(n)情况,假设通过O(n)和O(n²)的定义,我们给出C,X,K,Y,使得n>X⇒C·n> f(n)和n>Y⇒K·n²> g(n).设J = C·K,Z = max(X,Y).然后n>Z⇒J·n³> f(n)·g(n)证明f(n)·g(n)是O(n³).