2

所以我得到了一个函数，我会改变这个函数，因为它是家庭作业，我想学习如何做到这一点，而不是被告知答案是什么。

使用 big-Oh 和 Ω 的定义，找到以下表达式的上限和下限。请务必说明 c 和 k 的适当值。

c 1 3 n + c 2 n 4，其中常数是正整数。

现在，我了解如何确定类中的函数 f(n) ∈ O(g(n)) 还是 af(n) ∈ Ω(g(n)。

我不明白的是，如果你只有 f(n)，如何确定 g(n)。我希望这是有道理的！

编辑：我相信你可以强行将它插入到 g(n) 的一堆函数中，但如果有更好的解决方案，那并不是我真正想要的。

Edit2：我们不能为此使用限制方法，他们希望我们以某种方式使用基本定义。

编辑 3：以下是我们给出的定义：

这是我对 Big O 的看法：

对于 T(n) 一个非负值函数，如果存在两个正常数 c 和 k 使得 T(n)，则 T(n) 在集合 O(f(n)) 中<=c*f(n) 对于所有 n > k。

对于 Ω：

对于 T(n) 一个非负值函数，如果存在两个正常数 c 和 k 使得 T(n) >= c*g，则 T(n) 在集合 Ω(g(n)) 中(n) 对于所有 n > k

4

1 回答 1

1

直觉是 f ∈ O(g) 意味着 g 在某种程度上等于或大于 f；并且 f ∈ Ω(g) 意味着 g 在某种程度上等于或小于 f。在我的回答中，我不会对如何选择常数过于精确/挑剔。

首先要热身，你应该说服自己

  • f ∈ O(f) 和 f ∈ Ω(f)。（在定义中让 c=1, k=1）。
  • 如果 f ∈ O(g)，则 g ∈ Ω(f)，反之亦然。（如果你找到一个常数 (c,k)，那么 (1/c, k) 是你需要的常数）
  • 如果 f ∈ O(g) 则 f ∈ O(P*g) 和 Q*f ∈ O(g) 对于任何正常数 P,Q。这意味着将函数乘以正常数并不重要。Ω 也是如此。
  • 如果 f ∈ O(g) 且 f ∈ O(h)，则 f ∈ O(MIN(g,h))。
  • 如果 f ∈ Ω(g) 且 f ∈ Ω(h)，则 f ∈ Ω(MAX(g,h))。

当您试图找到 f+g 的 O 或 Ω 时，您通常会猜测 O(f) 或 O(g) 或 Ω(f) 或 Ω(g)。

在您的 3^n + n^4 的情况下，我们知道 3^n ∈ O(3^n)、n^4 ∈ O(n^4) 和 3^n + n^4 ∈ O(3^n + n^4)。但我们想做得更好。我们要证明 3^n + n^4 ∈ O(3^n + 3^n) = O(3^n)。如果我们可以证明 n^4 ∈ O(3^n)，我们就可以做到这一点。

我们应该完全按照定义所说的去做：证明存在 (c,k) 使得对于所有 n>k

n^4 ≤ c3^n
4log(n) ≤ log(c) + nlog(3)
4log(n) - nlog(3) ≤ log(c)

证明这个 c 总是存在的一种方法是使用微积分：证明 4log(n) - nlog(3) 最终是一个递减函数。导数是 4/n - log(3)，我们可以看到，对于足够大的 n，它是负数。因此，对于足够大的 n，4log(n) -nlog(3) 正在减少。因此，存在一个不等式成立的正常数 c。因此 n^4 ∈ O(3^n)。并且 3^n + n^4 ∈ O(3^n + 3^n) = O(3^n)。

因为 3^n + n^4 ≥ 1*3^n，3^n + n^4 ∈ Ω(3^n)。为了说明常量无关紧要，让我们使用您拥有的 c_1 和 c_2：c_1*3^n + c_2*n^4。令 d := min(c_1, c_2)。然后

c_1*3^n + c_2*n^4 ≥ d(3^n + n^4) ≥ d*3^n

所以 c_1*3^n + c_2*n^4 ∈ Ω(3^n)。类似地，使用 O(3^n)：让 d := max(c_1, c2)。那么对于足够大的n，

c_1*3^n + c_2*n^4 ≤ d(3^n + n^4) ≤ d(c*3^n) = (dc)*3^n

我们知道这个 c 存在是因为 3^n + n^4 ∈ O(3^n)。因此 c_1*3^n + c_2*n^4 ∈ O(3^n)。

不确定我的回答是否充分，但希望对您有所帮助。

于 2013-02-09T04:11:49.903 回答