证明和反驳BigO

Question

在证明和反驳明确表示使用定义来证明和反驳的大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

你的技术都不奏效.让我们从big-O的定义开始:

如果存在C,N,则f为O(g),使得| f(x)| ≤C| g(x)| 对于所有x≥N

要证明"存在"类型语句,您需要证明存在的东西.在大O证明的情况下,你通常会发现这些东西,虽然存在的证据通常不需要是建设性的.要为"为所有人"声明建立证据,假装某人只是递给你特定的价值观.请注意,不要对其属性进行隐式假设(您可以显式声明属性,例如N> 0).

在证明大O的情况下,你需要找到ç和ñ.显示| 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,存在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⇒电子商务样张^X > X ²和"n不是O(LN N)" ⇒ "n不为O(log _b n)的"左作为练习.