math - 显示一个 log n + bn = O(n log n) 而不管 a 和 b

Question

我需要帮助来理解 Big-O 问题。我明白了这个概念并且已经做了一些练习题，但是这个让我很难过。

使用大 O 的定义，证明f(n)=anlogn+bn是O(nlogn). (a, b > 0)

我不知道如何找到 C 或 N，因为如果常数 A 或 B 改变，那么 C 和 N 也必须改变？还是我看错了？

我有一个测试即将到来，我真的很想事先了解这一点。

谢谢！

Answer 1

当您收到这样的声明时：

证明 log n + bn = O(n log n)

您可以将其视为以下内容：

对于 a 和 b 的任意选择，证明 log n + bn = O(n log n)

这又意味着

_{对于 a 和 b 的任何选择，对于任何 n ≥ n 0}，都有一些 c 和 n ₀的选择，使得 log n + bn ≤ cn log n 。

换句话说，你首先选择 a 和 b，然后证明 an log n + bn = O(n log n)。您并不是要证明在 big-O 符号的定义中存在固定的 c 和 n ₀，而不管 a 和 b，而是应该表明，无论某人如何选择 a 和 b，您总是能够找到 ac 和 n ₀ ——这可能取决于 a 和 b ——使得 log n + bn = O(n log n) 使用 c 和 n ₀的选择。

要了解在此示例中如何执行此操作，可能有用的一个观察结果是（假设我们的日志以 2 为底），只要 n ≥ 2，1 ≤ log n。因此，只要我们限制 n 使得n≥2，我们得到

an log n + bn ≤ an log n + bn log n = (a + b) n log n

鉴于此，您知道如何选择 c 和 n ₀吗？我们限制 n 使得 n ≥ 2，因此选择 n ₀ = 2 是有意义的。同样，由于我们刚刚证明了 log n + bn ≤ (a + b) n log n，我们可以选择 c = a + b。

你可以把这个论点想象成两个人之间的对话：

• 其他人：我会选择 a 和 b，但我不会告诉你它们是什么。
• 你：嗯，好的。
• 其他人：所以向我证明存在 n ₀和 c 使得 log n + bn ≤ cn log n 每当 n ≥ n ₀时。
• 你：当然！尝试选择 c = a + b 和 n ₀ = 2。这样行吗？
• 别人：嘿，你是对的！那行得通！

请注意，对话以对方选择 a 和 b 开始。这样，您可以调整您对 c 和 n ₀的选择，以确保声明成立。如果您先尝试选择 c 和 n ₀，他们总能找到会破坏它的 a 和 b。

希望这可以帮助！

Answer 2

由于AandB是常数，可以用and来表达Cand 。例如，您可以证明并且足以证明。NABC=A+BN > 2Af(n) = O(n lg n)

Answer 3

也许我遗漏了一些东西，但这似乎不是 Big-O 的典型用法。您的函数是一个简单的数学函数，而不是算法。如果：

f(n)=anlog(n)+bn

那么复杂度是(anlog(n))和(bn)的更高的，假设加运算的复杂度可以忽略不计。因为 b 是常数，所以 (bn) 是 O(n)，同样，就像 a 是常数，(anlog(n)) 是 O(nlog(n))。