如何证明 5n=O(nlogn)
我把这个作为作业问题，但不记得在课堂上学过。有人可以为我指明正确的方向，或者提供有关如何解决此类问题的文档吗？
I have this as a homework question and don't remember learning it in class. Can someone point me in the right direction or have documentation on how to solve these types of problems?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
更正式地说...
首先，我们证明如果
f(n) = 5n，则f ∈ O(n)。为了证明这一点，我们必须证明对于一些足够大的k和i ≥ k，f(i) ≤ ci。幸运的是，c = 5使这变得微不足道。接下来，我将证明对于所有
f ∈ O(n)，f ∈ O(n * log n)。因此，我们必须证明，对于一些足够大的k，所有i ≥ k，f(i) ≤ ci * log i。因此，如果我们让k足够大，使得f(i) ≤ ci且i ≥ 2，那么结果是微不足道的，因为 <代码>ci ≤ ci * log i。量子ED。
More formally...
First, we prove that if
f(n) = 5n, thenf ∈ O(n). In order to show this, we must show that for some sufficiently largekandi ≥ k,f(i) ≤ ci. Fortunately,c = 5makes this trivial.Next, I'll prove that for all
f ∈ O(n)thatf ∈ O(n * log n). Hence, we must show that for some sufficiently largek, alli ≥ k,f(i) ≤ ci * log i. Hence, if we letkbe large enough thatf(i) ≤ ci, andi ≥ 2, then the result is trivial sinceci ≤ ci * log i.QED.
查看大 O 表示法的定义。这意味着 5n 的运行速度不会比 nlogn 慢，这是事实。 nlogn 是要执行的操作数的上限。
Look into the definition of big-O-notation. It means that 5n will run no slower the nlogn, which is true. nlogn is an upper bound of the number of operations to be performed.
您可以通过将 L'Hopitals 规则应用于 lim n-> 来证明这一点。 5n/nlogn 的无穷大
g(n) = 5n 和 f(n)=nlogn
求导 g(n) 和 f(n) 所以你会得到类似这样的东西
5/(这里的一些东西将包含 n)
5/infinity = 0 所以 5n = O(nlogn) 为真
You can prove it by applying L'Hopitals rule to lim n-> infinity of 5n/nlogn
g(n) = 5n and f(n)=nlogn
Derivate g(n) and f(n) so you will get something like this
5/(some stuff here that will contain n)
5/infinity = 0 so 5n = O(nlogn) is true
我不记得正式定义的措辞，但你必须显示的是：
c1 * 5 * n < c2 * n * logn, n>c3
其中 c1 和 c2 是任意常数，对于某个数字 c3。根据 c1 和 c2 定义 c3，就完成了。
I don't remember the wording of the formal definition, but what you have to show is:
c1 * 5 * n < c2 * n * logn, n>c3
where c1 and c2 are arbitrary constants, for some number c3. Define c3 in terms of c1 and c2, and you're done.
我已经三年没接触过大O的东西了。但我认为你可以尝试证明这一点：
O(5n) = O(n) = O(nlogn)
O(5n) = O(n) 很容易证明，所以你现在要做的就是证明 O (n) = O(nlogn) 这也不应该太难。
It's been three years since I touched big-O stuff. But I think you can try to show this:
O(5n) = O(n) = O(nlogn)
O(5n) = O(n) is very easy to show, so all you have to do now is to show O(n) = O(nlogn) which shouldn't be too hard too.