大哦，定义的后果

Question

我花了很多时间在这里和 math.stackexchange 上阅读有关 Big-Oh 的问题和答案，似乎这是最好的地方，因为 math.stackexchange 似乎不喜欢这类问题。因此，我在大学的 CS 类(class)中给了我一些类(class)作业，但我并不完全理解它，希望你们能提供帮助。我知道“作业”问题在这里有点不受欢迎，所以我选择了另一个例子，即 不是 我的类(class)的一部分，但是 是 类似的风格。

所以这里是我在注释中给出的定义:


我得到的问题是:

使用定义 2.5 表明，如果 f(n) 是 O(g(n))，那么 k + f(n) 也是 O(g(n))。

我花了 3 天时间在网上搜索此类问题的任何类型的答案。查看定义 2.5，它说 f(n) 是 O(g(n))，k + f(n) 是 O(g(n))。这对我来说已经足够了，但似乎我必须证明它是如何推导出来的。起初我认为应该通过归纳来完成，但后来决定反对，必须有一种更简单的方法。

任何帮助，将不胜感激。我不指望有人正直地给我答案。我更喜欢方法论或引用资料，以说明我可以在哪里学习这样做的技术。我可以再次提醒您这是不是 我的实际类(class)，但一个类似风格的问题。

提前致谢。

Answer 1

假设 f(n) 是 O(g(n))
那么存在一个 c 和一个 k' s.t.对于所有 n > k': f(n) <= cg(n)
现在考虑 f(n) + k
对于所有大于 k' 的 n，令 d 为 s.t k <= d*g(n)
您知道这是可能的，因为 k 在 O(1) 中
然后
f(n) + k <= cg(n) + dg(n) = (d+c)(g(n))
然后你使用定义并用 d+c 代替 c，==> f+k 在 O(g) 中