complexity-theory - 渐近符号：证明 Big Omega、O 和 Theta

Question

我有一些我没有完全掌握的渐近符号问题。

因此，在证明渐近复杂性时，我理解找到一个常数的操作以及该符号适用的 n0 项。因此，例如：

Prove 7n+4 = Ω(n)

在这种情况下，我们将选择一个常数 c，使其低于 7，因为这是关于 Big Omega。选择 6 将导致

7n+4 >= 6n

n+4 >= 0

n = -4

但是由于 n0 不能是负数，我们选择一个正整数，所以 n0 = 1。

但是像这样的问题呢：

Prove that n^3 − 91n^2 − 7n − 14 = Ω(n^3).

我选择 1/2 作为常数，达到

1/2n^3 - 91n^2 - 7n -14 >= 0.

但我不确定如何继续。另外，像这样的问题，我认为关于theta：

Let g(n) = 27n^2 + 18n and let f(n) = 0.5n^2 − 100. Find positive constants n0, c1 and c2 such
that c1f(n) ≤ g(n) ≤ c2f(n) for all n ≥ n0.

在这种情况下，我是否在这里执行两个单独的操作，一个大 O 比较和一个大 Omega 比较，以便存在 theta 关系或紧密绑定？如果是这样，我会怎么做？

标签： complexity-theory

Answer 1

为了证明 n ³ − 91n ² − 7n − 14 在 Ω(n ³ ) 中，我们需要展示一些数字 n ₀和 c，使得对于所有 n ≥ n ₀：

n ³ - 91n ² - 7n - 14 ≥ cn ³

你已经选择了 c = 0.5，所以让我们继续吧。重新排列给出：

n ³ − 0.5n ³ ≥ 91n ² + 7n + 14

两边都乘以 2 并化简：

182n ² + 14n + 28 ≤ n ³

对于所有 n ≥ 1，我们有：

182n ² + 14n + 28 ≤ 182n ² + 14n ² + 28n ² = 224n ²

当 n ≥ 224 时，我们有 224n ² ≤ n ³。因此，选择 n ₀ = 224 和 c = 0.5 表明原始函数在 Ω(n ³ ) 中。