algorithm - 证明和反驳 BigO

Question

在证明和反证 Big O 问题中明确说明使用定义来证明和反证，我的问题是，我做的是正确的吗？

例如，您有一个问题是 g(n) = O(f(n)) ... 为了证明这一点，我做了以下操作

g(n) <= C(F(n))
g(n)/F(n) <= C .. then give n=1 and solve for C , which proves it.

我在做这件事时遇到的矛盾是当我提出一个反驳这些东西的问题时

例如

g(n) =O(F(n)) 我会反驳它

g(n) >= C(F(n)) 并再次求解 C。然而，这让我相信大 O 可以立即被证明和反驳？这是 100% 错误的。

使用真实世界的数字(证明)

n^2 + 3 = O(n^2)
(n^2 + 3)/n^2  <= C  assume n = 1 then C >= 3

Disproving

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


(n^2 + 3)/n^2  >= C  assume n = 1 then C <= 3

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

这两个都说 @n =1 和 c = 3 算法是 O(n^2) 而不是 O(n^2)。

任何人都可以帮助我澄清我的困惑并帮助我学习解决大 O 问题的良好算法方法吗？

Answer 1

您的两种技术均无效。让我们从大 O 的定义开始:

f is O(g) iff there exist C, N such that |f(x)| ≤ C |g(x)| for all x ≥ N

要证明“存在”类型的陈述，您需要证明事物存在。在大 O 证明的情况下，你通常会找到东西，尽管存在证明通常不需要是 constructive。 .要为“适用于所有人”的陈述建立证明，请假装有人刚刚给了您特定的值。请注意不要对它们的属性做出任何隐含的假设(您可以明确说明属性，例如 N > 0)。

在证明big-O的情况下，你需要找到C和N。显示 |g(n)| ≤ C|F(n)|对于单个 n 是不够的。

例如“n²+3 是 O(n²)”:

 For n ≥ 2, we have:     n2 ≥ 4 > 3      ⇒ n2-1 > 2      ⇒ 2(n2-1) > (n2-1)+2      ⇒ 2n2 > (n2-1)+4 = n2+3 Thus n2+3 is O(n2) for C=2, N=2.

为了反驳，您对陈述进行否定:表明没有C 或N。换句话说，表明对于所有 C 和 N，存在一个 n > N 使得 |f(n)| > C |g(n)|。在这种情况下，C 和 N 是“对所有人”合格的，因此假装它们已被提供给您。因为 n 是限定“存在”的，所以你必须找到它。这是您从想要证明的方程式开始并向后工作直到找到合适的 n 的地方。

假设我们要证明 n 不是 O(ln n)。假设我们有 N 和 C，我们需要找到一个 n ≥ N 使得 n > C ln n。

For all whole numbers C, N, let M=1+max(N, C) and n = eM. Note n > N > 0 and M > 0.Thus n = eM > M2 = M ln eM = M ln n > C ln n. QED.

x > 0 ⇒ e^x> x² 和“n 不是 O(ln n)”⇒ “n 不是 O(log _b n)"留作习题。