证明和反驳BigO [英] Proving and Disproving BigO
问题描述
在证明和反对Big O问题中，明确指出使用定义来证明和反对的问题，我的问题是，我在做什么正确？
In proving and disproving Big O questions that explicitly say use the definition to prove and disprove, my question is, is what I am doing correct?
例如，您有一个问题是g（n）= O（f（n））...为了证明这一点，我在做以下事情
For example you have a question that is g(n) = O(f(n)) ... In order to prove it I was doing the following
g(n) <= C(F(n))
g(n)/F(n) <= C .. then give n=1 and solve for C , which proves it.
这样做的过程中，我遇到的矛盾是当我遇到一个反对这种东西的问题时
The contradiction that I run to when doing this is when i approach a question of disproving this stuff
例如
g（n）= O（F（n））来证明我会做
g(n) =O(F(n)) to disprove it I would do
g（n）> = C（F（n））并再次求解C。但是，这使我相信可以立即证明和反驳大O？这是100％错误。
g(n) >= C(F(n)) and solve for C again . However this leads me to believe that big O can be proved and disproved at once ? which is 100% wrong.
使用真实世界的数字
（证明）
Using real world numbers (Proving)
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）。
both of these say that @ n =1 and c = 3 the algorithm is O(n^2) and is NOT O(n^2).
谁能帮助我澄清我的困惑，并帮助我学习解决大O问题的良好算法方法？
Can anyone help me clarify my confusion and give me a help me learn a good algorithmic way of solving big O questions?
推荐答案
您的两种技术均无效。让我们从big-O的定义开始：
Neither of your techniques work. Let's start with the definition of big-O:
f是O（g），如果存在C，N使得| f（x ）| ≤ C | g（x）|对于所有x≥ N
f is O(g) iff there exist C, N such that |f(x)| ≤ C |g(x)| for all x ≥ N
要证明存在类型语句，您需要证明事物已经存在。对于big-O证明，您通常会找到东西，尽管存在的证明通常不需要建设性的。要为所有人声明建立证据，请假装有人刚刚为您提供了特定的价值。请注意，不要对它们的属性进行任何隐式假设（可以明确声明属性，例如N> 0）。
To prove "there exist" type statements, you need to show that, well, the things exist. In the case of big-O proofs, you usually find the things, though proofs of existence don't generally need to be constructive. To build a proof for a "for all" statement, pretend someone just handed you specific values. Be careful you make no implicit assumptions about their properties (you can explicitly state properties, such as N > 0).
在证明big-O的情况下，您可以需要找到 C 和 N 。显示| g（n）| ≤C | F（n）|
In the case of proving big-O, you need to find the C and N. Showing |g(n)| ≤ C|F(n)| for a single n isn't sufficent.
例如， n 2 +3是O（n 2 ）：
For the example "n2+3 is O(n2)":
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 。
To disprove, you take the negation of the statement: show there is no C or N. In other words, show that for all C and N, there exists an n > N such that |f(n)| > C |g(n)|. In this case, the C and N are qualified "for all", so pretend they've been given to you. Since n is qualified "there exists", you have to find it. This is where you start with the equation you wish to prove and work backwards until you find a suitable n.
假设我们要证明n不是O（ln n）。假设给定N和C，我们需要找到n≥ N使得n＞ 1。 Cln n。
Suppose we want to prove that n is not O(ln n). Pretend we're given N and C, and we need to find an n ≥ N such that 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 2 并且 n不是O（ln n）⇒剩下的练习是 n不是O（log b n）。
Proofs of x > 0 ⇒ ex > x2 and "n is not O(ln n)" ⇒ "n is not O(logb n)" left as exercises.
这篇关于证明和反驳BigO的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
