2

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

所以这是我在笔记中给出的定义： 替代文字

我得到的问题是：

使用定义 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))。这对我来说已经足够了，但似乎我必须证明它是如何得出的。起初我认为它应该以某种方式通过归纳来完成，但后来决定反对，必须有一种更简单的方法。

任何帮助，将不胜感激。我不指望有人会直截了当地给我答案。我更喜欢方法论或参考，以了解我可以在哪里学习这样做的技术。我能否再次提醒您，这不是我的实际课程作业，而是类似风格的问题。

提前致谢。

4

4 回答 4

2

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

于 2010-11-25T21:52:37.277 回答
1

f(n) <= cg(n)

k + f(n) <= c'g(n) 其中 c' = ck

所以 k + f(n) 是 O(g(n))

于 2010-11-25T22:02:42.330 回答
0

然后k是O(1)，f(n)是一个O(g(n))然后你可以总结这个值然后你有O(1+g(n))这个是O(g(n));

f(n)是O(g(n))那么k + f(n)也是O(g(n)), 因为你在你的书中写过

忽略常数的添加

常量总是被忽略，因为不能改变Big-O符号，任何常量都O(1)在Big-O符号中。

于 2010-11-25T21:52:59.050 回答
0

对于它的价值，这是一个有点做作的大 O 表示法的定义。更一般，在我看来，更直观的定义是，对于f(n) ~ O(g(n))一些有限实数。n->alim|f(n)/g(n)| <= An->aA

重要的部分是限制上下文是必需的。在 CS 中，该限制被隐含地视为无穷大（因为n随着问题大小的增加，这往往是），但原则上它可以是任何东西。例如，sin(x) ~ O(x)as x->0（事实上，它恰好是 渐近线x；这是小角度近似）。

于 2010-11-25T22:23:50.317 回答