证明不同的运行时具有不同的大O复杂性？
如何证明以下内容：
10 n log n ∈ O(2n2)
n log n + 40 · 2n - 6n ∈ O(2n)
在第一个中，我使用这个数学：
10 n log n ≤ c · 2n2
10 n2 ≤ c · 2n2 除以 2
5 n2 ≤ c · n2
我猜测 c = 5 且 n0 = 1，但我不确定这是否属实。
在第二个中，我尝试将左侧乘以 2n 但最终没有成功。有人有什么建议吗？
How can I prove the following:
10 n log n ∈ O(2n2)
n log n + 40 · 2n - 6n ∈ O(2n)
In the first one, I'm using this math:
10 n log n ≤ c · 2n2
10 n2 ≤ c · 2n2 divide by 2
5 n2 ≤ c · n2
I'm guessing that c = 5 and n0 = 1, but I'm not sure if that's true.
In the second one, I tried to multiply the left hand side by 2n but that didn't end up working. Does anyone have any suggestions?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
对于第 (1) 部分，您想要证明
注意到对于任何 n ≥ 1 可能会有所帮助
因此，你有
因此，您可以得出结论： 10n log n = O(2n2)因为您可以选择 n0 = 1 和 c = 5 并使用 big-O 的正式定义。
对于第 (i) 部分，您想证明
您可能想在此处使用的一个有用事实是 n2 ≤ 2n 对于任何 n ≥ 4。因此，我们得到，每当 n ≥ 4
因此，如果您选择 n0 = 4 且 c = 41，则可以使用 big-O 的正式定义来证明 n log n + 40 · 2n - 6n = O(2n)。
希望这有帮助！
For part (1), you want to prove
It might help to note that for any n ≥ 1 that
Therefore, you have that
Therefore, you can conclude that 10n log n = O(2n2) because you can choose n0 = 1 and c = 5 and use the formal definition of big-O.
For part (i), you want to prove
One useful fact you might want to use here is that n2 ≤ 2n for any n ≥ 4. Therefore, we get that, whenever n ≥ 4
Therefore, if you pick n0 = 4 and c = 41, you can use the formal definition of big-O to prove that n log n + 40 · 2n - 6n = O(2n).
Hope this helps!