Chứng minh và giải quyết BigO

Question

Trong việc chứng minh và bác bỏ các câu hỏi của Big O nói rõ ràng sử dụng định nghĩa để chứng minh và bác bỏ, câu hỏi của tôi là, là những gì tôi đang làm đúng?

Ví dụ bạn có một câu hỏi đó là g (n) = O (f (n)) ... Để chứng minh điều đó tôi đã làm như sau

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

Các mâu thuẫn mà tôi chạy đến khi làm điều này là khi tôi tiếp cận một vấn đề bác bỏ công cụ này

ví dụ

g (n) = O (F (n)) để bác bỏ nó tôi sẽ làm

g (n)> = C (F (n)) và giải quyết cho C một lần nữa. Tuy nhiên điều này khiến tôi tin rằng O lớn có thể được chứng minh và bác bỏ ngay lập tức? 100% sai.

Sử dụng số thế giới thực (Chứng minh)

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) 

cả hai nói rằng @ n = 1 và c = 3 thuật toán là O (n^2) và là KHÔNG O (n^2) .

Bất kỳ ai có thể giúp tôi làm rõ sự nhầm lẫn của mình và giúp tôi tìm hiểu cách giải thuật tốt nhất để giải quyết các câu hỏi O lớn?

Answer 1

Cả kỹ thuật của bạn đều không hoạt động. Hãy bắt đầu với định nghĩa của big-O:

f là O (g) iff tồn tại C, N sao cho | f (x) | ≤ C | g (x) | cho tất cả x ≥ N

Để chứng minh "có tồn tại" loại câu lệnh, bạn cần chứng minh rằng, những thứ tồn tại. Trong trường hợp chứng minh O-lớn, bạn thường tìm thấy những điều, mặc dù bằng chứng về sự tồn tại thường không cần phải là constructive. Để xây dựng một bằng chứng cho một tuyên bố "cho tất cả", giả vờ một người nào đó chỉ trao cho bạn các giá trị cụ thể. Hãy cẩn thận bạn không đưa ra các giả định tiềm ẩn về các thuộc tính của chúng (bạn có thể nêu rõ các thuộc tính, chẳng hạn như N > 0).

Trong trường hợp chứng minh big-O, bạn cần tìm số C và N. Đang hiển thị | g (n) | ≤ C | F (n) | cho một n không phải là sufficent.

Đối với ví dụ "n 3 là 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. 

Để bác bỏ, bạn hãy phủ định của tuyên bố: hiển thị không có C hoặc N. Nói cách khác, hãy hiển thị rằng đối với tất cả C và N, tồn tại một n > N sao cho | f (n) | > C | g (n) |. Trong trường hợp này, C và N đủ điều kiện "cho tất cả", vì vậy giả sử chúng đã được trao cho bạn. Vì n đủ điều kiện "tồn tại", bạn phải tìm nó.Đây là nơi bạn bắt đầu với phương trình bạn muốn chứng minh và làm việc ngược cho đến khi bạn tìm thấy n phù hợp.

Giả sử chúng tôi muốn chứng minh rằng n không phải là O (ln n). Giả sử chúng tôi được cung cấp N và C, và chúng tôi cần tìm một số n ≥ N sao cho 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. 

Bằng chứng của x e ^x > x và "n không phải là O (ln n)" ⇒ "n không phải là O (log _b n)" trái như bài tập .