big-o - 面试问题

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) 的 o(n²) 下限，但你没有得到上限在 f(n) + g(n) 上，因为在 f(n) 上没有给出上限。[注意，在上面，Θ 是一个大 θ 或大 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) = cn + d
g(n) = an^2 + bn + p

然后，
f(n) + g(n) = an^2 + (n 的低幂)
并且，
f(n).g(n) = xn^3 + (n 的低幂)

由此得出 O(f(n) + g(n)) = O(n^2)

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

Answer 4

这个问题可以这样理解：-

f(n)=O(n) 表示计算 f(n) 需要 O(n) 时间。

相似地，

对于需要 O(n^2) 时间的 g(n)

所以，

P(n)=f(n)+g(n) 肯定会占用 O(n)+O(n^2)+O(1)（另外，一旦你知道 f 和 g 的值）

. 因此，这个新功能

P(n) 需要 O(n^2) 时间。

情况也是如此

Q(n) =f(n)*g(n) 这需要 O(n^2) 时间

.