math - 如何证明 3n + 2log n = O(n)

Question

如何使用 big-O 的定义证明 3n + 2log n = O(n)？

C 应该是 6，而 k 是 1，但我不知道它是如何找到的。很多帮助将不胜感激。

Answer 1

为了正式证明这个结果，你需要找到一个 n ₀和 c 的选择，使得

对于任何 n ≥ n ₀ : 3n + 2log n ≤ cn

首先，请注意，如果您有任何 n ≥ 1，则 log n < n。因此，如果你考虑任何 n ≥ 1，你有

3n + 2log n < 3n + 2n = 5n

因此，如果你选择 n ₀ = 1 和 c = 5，你有

对于任意 n ≥ n0：3n + 2log n < 3n + 2n = 5n ≤ cn

因此 3n + 2 log n = O(n)。

更一般地说，当给定这样的问题时，尝试识别主导项（这里是 n 项）并尝试找到一些 n ₀的选择，以使非主导项被主导项压倒。完成此操作后，剩下要做的就是选择正确的常数 c。

希望这可以帮助！

Answer 2

疯狂的猜测（你的问题很不清楚）：任务是证明

O(3n + 2log n) = O(n)

现在结果是这样的：n -> n增长速度比 快n -> log n，并且由于复杂性是渐近的，所以只有增长最快的项才重要，n在这种情况下就是这样。

Answer 3

如果我没记错的话，你可以证明以下几点：如果 f1(n)=O(g1(n)), f2(n)=O(g2(n)) 那么 f1(n)+f2(n)=O(max {g1(n),g2(n)})。从那里开始很简单。