证明如果 g(n) 是 o(f(n)), 那么 f(n) + g(n) 是 Theta(f(n))。

Question

证明如果 g(n) 是 o(f(n)), 那么 f(n) + g(n) 是 Theta(f(n))。

algorithmmathtime-complexitylittle-o

3

所以，我正在为证明（或驳斥）上述问题而苦苦挣扎。我觉得这是真的，但我不确定如何展示它。

再次强调，问题是如果g(n)是小o(f(n)),那么f(n)+g(n)是Theta(f(n))。

请注意，这是小o，不是大O！

到目前为止，我已经成功地（轻松地）展示了：

g(n)=o(f(n))-->g(n)

然后，g(n)+f(n)<(c+1)*f(n)--> (g(n)+f(n))=O(f(n))

然而，对于显示大Omega，我不确定该怎么做。

我这样做对吗？

编辑：每个人都提供了巨大的帮助，但我只能选择一个。谢谢。

- Wanna-be Coder

3个回答

1

在开始之前，让我们先说明一下小o和大Theta符号的含义：

Little-o notation

Formally, that g(n) = o(f(n)) (or g(n) ∈ o(f(n))) holds for sufficiently large n means that for every positive constant ε there exists a constant N such that
|g(n)| ≤ ε*|f(n)|, for all n > N                                 (+)

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

Big-Θ notation

h(n) = Θ(f(n)) means there exists positive constants k_1, k_2 and N, such that k_1 · |f(n)| and k_2 · |f(n)| is an upper bound and lower bound on on |h(n)|, respectively, for n > N, i.e.
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 = 2，以及h(n) = g(n)+f(n)。因此，

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

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

- dfrib

谢谢您提供这样深入的回答。所有内容综合起来真的非常有帮助！ - Wanna-be Coder

@Wanna-beCoder 很高兴能帮忙。 - dfrib

1

到目前为止都很好。

接下来，回想一下在最好的情况下，0 <= g(n)；这应该可以给出g(n) + f(n)的一个下界。

- comingstorm

是的，我考虑过在两边都加上另一个c*f(n)，因为我们实际上想要的形式是c1f(n) < f(n) + g(n) < c2f(n),但这样做感觉不太对，因为我们在中间有额外的常数，比如c1*f(n) < (c1+1)f(n) + g(n) < (c1 + c2)*f(n),但这似乎不是一个有效的改变，因为中间项应该看起来正好像我们想要的一样，对吧？ - Wanna-be Coder

不，根据“0 <= g(n)”这个事实，你有“f(n) <= g(n) + f(n)” 。将其与你已经得到的不等式结合起来，你就有了下限和上限... - comingstorm

你不需要一些与左侧的f(n)配对的常数来满足Theta的条件吗？ - Wanna-be Coder

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

一种方法是在n趋向无穷大时取(f(n) + g(n)) / f(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))的含义）。