证明复杂性阶证明如果f(n)是Ω(n*g(n)

Question

证明如果f(n(是Ω(n*g(n((，则f(n

假设f(n(是Ω(n*g(n((，f(n"是O(g(n((。需要表现出矛盾。方法是找到一个违反定义的n值。证明：f(n(是Ω(n*g(n((暗示存在正值C和k，使得n>k表示f(n(≥C*n*g(n(。f(n(是O(g(n((意味着存在正值C′和k′，使得n>k′表示f(n(≤C*g(n(。

那么，n的哪个值违反了定义，我怎么能表现出矛盾呢？

Answer 1

通过矛盾来证明语句的方法是可行的。但首先，你需要更精确一点：

1. f和g是整数上的正非递减函数
2. C和C'是>=0
3. 你最后的含义应该是C' * g(n)(而不是C * g(n)(

所以我们从开始

(a( 存在正整数C、C'、k、k'，使得对于所有的n > k和n' > k'：

C * n * g(n) <= f(n) and f(n') <= C' g(n')

通过将你的两个含义链接在一起，并将两个通用量词合并为一个(注意到for all n > k and n' > k'意味着for all n > max(k,k')(，你会立即得到：

(b( 存在正整数C、C'、k、k'，使得对于所有的n > max(k,k'):

C * n * g(n) <= C' g(n)

除以两边的g(n)，这在假设1中是有效的。以上，产生等价物：

(c( 存在正整数C、C'、k、k'，使得对于所有n > max(k,k')：

C * n <= C'

这相当于：

(d( 存在正整数C、C'、k、k'，使得对于所有n > max(k,k')：

n <= C'/C

最后一个语句相当于false。这是一个矛盾，因此最初的说法是正确的。