2

所以我正在努力证明（或反驳）上述问题。我觉得这是真的，但我不知道如何表现出来。

同样，问题是如果 g(n) 是 o(f(n))，那么 f(n) + g(n) 是 Theta(f(n))

请注意，这是一个little-o，而不是一个 big-o ！！！

到目前为止，我已经设法（轻松地）证明：

g(n) = o(f(n)) -> g(n) < c*f(n)

那么 g(n) + f(n) < (c+1)*f(n) -> (g(n) + f(n)) = O (f(n))

但是，为了展示 Big Omega，我不知道该在那里做什么。

我这样做对吗？

编辑：每个人都提供了很大的帮助，但我只能标记一个。谢谢你。

4

3 回答 3

2

一种选择是采用 (f(n) + g(n)) / f(n) 的限制，因为 n 趋于无穷大。如果这收敛到一个有限的非零值，则 f(n) + g(n) = Θ(f(n))。

假设对于足够大的 n，f(n) 不为零，则上述比率在极限范围内为

(f(n) + g(n)) / f(n)

= f(n) / f(n) + g(n) / f(n)

= 1 + g(n) / f(n)。

因此，当 n 趋于无穷时取极限，上述表达式收敛到 1，因为比率变为零（这就是 g(n) 为 o(f(n) 的含义）。

于 2016-01-18T21:33:38.780 回答
1

在开始之前，让我们先说明 little-o 和 Big-Theta 符号的含义：

小o符号

形式上，那个g(n) = o(f(n))（或g(n) ∈ o(f(n))）成立足够大n意味着对于每个正常数都ε 存在一个常数N，使得

|g(n)| ≤ ε*|f(n)|, for all n > N                                 (+)

来自https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation。

大 Θ 符号

h(n) = Θ(f(n))表示存在正常数k_1,k_2 和N, 使得k_1 · |f(n)|和分别k_2 · |f(n)|是 上的上界和下界|h(n)|, 对于n > N, 即

k_1 · |f(n)| ≤ |h(n)| ≤ k_2 · |f(n)|, for all n > N              (++)

来自https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation。

鉴于： g(n) ∈ o(f(n))

因此，在我们的例子中，对于每个ε>0我们都可以找到一些常数N，使得(+)，对于我们的函数g(n)和f(n)。因此，对于n>N，我们有

|g(n)| ≤ ε*|f(n)|, for some ε>0, for all n>N

Choose a constant ε < 1 (recall, the above holds for all ε > 0), 
with accompanied constant N. 
Then the following holds for all n>N

    ε(|g(n)| + |f(n)|) ≤ 2|f(n)| ≤ 2(|g(n)| + |f(n)|) ≤ 4*|f(n)|    (*)

去掉最左边的不等式(*)并除以 2，我们有：

|f(n)| ≤ |g(n)| + |f(n)| ≤ 2*|f(n)|, n>N                            (**)

我们看到，这就是 Big-Θ 符号的定义，如 中所示，(++)带有常量k_1 = 1和。因此k_2 = 2h(n) = g(n)+f(n)

(**) => g(n) + f(n) is in Θ(f(n))

Ans 我们已经证明这g(n) ∈ o(f(n))意味着(g(n) + f(n)) ∈ Θ(f(n))。

于 2016-01-19T14:18:05.200 回答
1

到目前为止，一切都很好。

对于下一步，请记住，在最好的情况下，0 <= g(n); 这应该让你对g(n) + f(n).

于 2016-01-18T21:33:44.330 回答