complexity-theory - 复杂度分析 - 添加 2 个函数

Question

我有一个家庭作业问题

Given f(n) is O(k(n)) and g(n) is O(k(n)), prove f(n)+g(n) is also O(k(n))

我不确定从哪里开始，有什么帮助可以指导我如何解决这个问题吗？

Answer 1

尝试并在逻辑上完成它。 f(n)以线性速率增加。也是如此g(n)。所以

O(n) + O(n) = O(2n)

当试图找到一个函数的大 O 分类时，常量不计算在内。我会把剩下的（包括为什么）留给你练习。（获得关于 SO 的完整答案将是作弊！）

Answer 2

请参阅Big-Oh 表示法的规则。

求和规则：如果f(n)isO(h(n))和g(n)is O(p(n))，那么f(n)+g(n)is O(h(n)+p(n))。

对您的情况使用此规则的复杂性将是O(2k(n))，这不过是O(k(n))。

Answer 3

因此，对于任意大的 n 值，如果 f(n) 小于或等于 g(n) 的某个正常数倍数，则 f(n) 为 O(g(n))（因此：f(n) <= cg(n) 对于 n >= n_0)。通常，为了证明某事是 O(g(n))，我们提供一些 c 和 n_0 来证明它是真的。

在您的情况下，我将从使用该定义开始，因此您可以说 f(n) <= ck(n) 和 g(n) <= dk(n)。我不想为你完全回答这个问题，但你基本上只是想证明 f(n)+g(n) <= tk(n)。

*c、d 和 t 都是任意的正常数。如果您需要更多帮助，请发表评论，我很乐意提供更多信息。