大哦，定义的后果
我花了很多时间在这里和 math.stackexchange 上阅读有关 Big-Oh 的问题和答案，似乎这是最好的地方，因为 math.stackexchange 似乎不喜欢此类问题。因此，我在大学获得了一些关于计算机科学课程的课程作业，但我并不完全理解它，希望你们能提供帮助。我知道“家庭作业”问题在这里有点不受欢迎，所以我选择了另一个例子，它不是我的课程作业的一部分，但是类似的风格。
这是我在注释中给出的定义： 
我得到的问题是：
使用定义 2.5 表明如果 f( n) 是 O(g(n))，那么 k + f(n) 也是 O(g(n))。
我花了三天时间在网上搜索此类问题的任何答案。看看定义 2.5，它说 f(n) 是 O(g(n))，k + f(n) 是 O(g(n))。这对我来说已经足够了，但看来我必须证明它是如何得出的。我一开始认为应该通过归纳法来完成，但后来决定不这样做，并且必须有一种更简单的方法。
任何帮助将不胜感激。我并不指望有人能正直地给我答案。我更喜欢一种方法或参考，以便我可以在哪里学习执行此操作的技术。我可以再次提醒您，这不是我的实际课程作业，而是类似风格的问题。
提前致谢。
I have spent a lot of time reading questions and answers about Big-Oh on both here and math.stackexchange and seems that this is the best place for it as math.stackexchange don't seem to like questions of this sort. So I have been given some coursework at uni on my CS course and I don't fully understand it and was hoping you guys could help. I understand that "homework" questions are slightly frowned upon here so I have chosen another example that is not part of my coursework, but is of similar style.
So here is the definition that I have been given in the notes:
And the question I have been given is:
Using Definition 2.5 show that if f(n) is O(g(n)) then k + f(n) is also O(g(n)).
I have spent 3 days searching the web for any kind of answer to problems like these. Looking at definition 2.5 it says f(n) is O(g(n)) and k + f(n) is O(g(n)). That's enough for me, but it seems I have to prove how that is derived. I thought at first that it should be done somehow by induction but have since decided against that and there must be a simpler way.
Any help would be appreciated. I don't expect someone to just upright give me the answer. I would more prefer either a methodology or a reference to where I can learn the technique of doing this. Could I remind you again that this is not my actual coursework but a question of similar style.
Thanks in Advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
假设 f(n) 是 O(g(n))
那么对于所有 n > 存在 ac 和 k' st k': f(n) <= cg(n)
现在考虑 f(n) + k
对于所有大于 k' 的 n，令 d 为 st 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)
suppose f(n) is O(g(n))
then there exists a c and a k' s.t. for all n > k': f(n) <= cg(n)
now consider f(n) + k
let d be s.t k <= d*g(n) for all n greater than k'
which you know is possible because k is in O(1)
then
f(n) + k <= cg(n) + dg(n) = (d+c)(g(n))
Then you use the definition and substitute d+c for c, ==> f+k is in O(g)
f(n) <= cg(n)
k + f(n) <= c'g(n)
其中 c' = ck
所以 k + f(n) 是 O(g(n))
f(n) <= cg(n)
k + f(n) <= c'g(n)
where c' = ck
so k + f(n) is O(g(n))
那么
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 表示法，任何常量都是
Big-O中的O(1)> 符号。Then
kisO(1),f(n)is aO(g(n))then you can sum this values then you haveO(1+g(n))this isO(g(n));f(n)isO(g(n))thenk + f(n)is alsoO(g(n)), because you have writed in your bookConstant are always ignored because can't change Big-O notation, any constant is
O(1)inBig-Onotation.无论如何，这是大 O 表示法的一个有点人为的定义。在我看来，更一般、更直观的定义是
f(n) ~ O(g(n))asn->aifflim|f(n)/g(n)|对于某些有限实数相当于A，<= An->a。重要的是需要一个限制上下文。在计算机科学中，该限制被隐含地视为无穷大（因为随着问题规模的增加，n 趋向于无穷大），但原则上它可以是任何东西。例如，
sin(x) ~ O(x)为x->0（事实上，它完全渐近于x；这是小角度近似）。For what it's worth, this is a somewhat contrived definition of big-O notation. The more general and, in my opinion, more intuitive definition is that
f(n) ~ O(g(n))asn->aifflim|f(n)/g(n)| <= Aasn->afor some finite real numberA.The important part is that a limit context is required. In CS, that limit is taken implicitly to be infinity (since this is what
ntends to as the problem size increases), but in principle it can be anything. For example,sin(x) ~ O(x)asx->0(in fact, it's exactly asymptotic tox; this is the small angle approximation).