面试问题

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²)。

从f(n) = o(n)和g(n) =Θ(n²)可以得到f(n) + g(n)的下界，但没有得到f(n) + g(n)的上界，因为没有给出f(n)的上界。请注意，在上面的代码中，Θ是一个big-θ或big theta

对于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²)，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³)。

Answer 2

O(f(n) + g(n)) = O(max{f(n), g(n)}) 

所以首先

f(n) + g(n) = O(max{n, n^2}) = O(n^2)

为

f(n) ⋅ g(n) 

我们将会有

O(f(n) ⋅ g(n)) = O(n ⋅ n^2) = O(n^3)

Answer 3

这样想吧。

f(n) = c.n +d

g(n) = a.n^2 + b.n +p

然后,

f(n) + g(n) = a.n^2 +(n的低幂)

和,

f( n) .g(n) = x.n^3 +(n的低次幂)

证明了O(f(n) + g(n)) = O(n^2)

和O(f(n).g(n)) = O(n^3)