Làm thế nào để chứng minh quan hệ lớn-o

Question

Hey, tiêu đề có thể là một chút tắt, vì vậy hãy sửa nó nếu bạn biết làm thế nào để đặt nó tốt hơn.

Như một bài tập về nhà tôi đã được trao nhiều nhiệm vụ cùng như sau:

Hãy f (n) và g (n) có chức năng tiệm cận tích cực. Chứng minh hoặc bác bỏ từng giả thuyết sau đây.

a. f(n) = O(g(n)) implies g(n) = O(f(n)) 

Bây giờ, câu hỏi thực sự của tôi là - bạn sẽ chứng minh điều này một cách chính thức như thế nào? Tôi biết rằng ở trên sẽ dễ dàng như tôi có thể dễ dàng cung cấp một ví dụ truy cập để bác bỏ nó, nhưng vì lợi ích của lập luận, chúng ta hãy nói rằng chúng ta muốn làm điều này mà không cần ví dụ truy cập, như tất nhiên điều này tiếp tục với một số ví dụ khác điều này sẽ không hoạt động.

Tôi là một chút khó khăn, tôi đã bất bình đẳng sau đây viết lên (với < = là ít hơn hoặc bằng)

f(n) <= c1 * g(n) 
g(n) <= c2 * f(n) 

Nhưng tôi không chắc chắn như thế nào tôi sẽ kết hợp những 2 bất phương trình thành một đơn (trong) phương trình và bác bỏ nó. Tôi chắc chắn nhất rằng đây là điều khá dễ dàng mà tôi đã bỏ qua và hiện tại tôi khá ngu ngốc - nhưng bất kỳ con trỏ/ví dụ cụ thể nào về cách làm điều này sẽ tuyệt vời, để tôi có thể làm việc phần còn lại của những câu hỏi này ra một mình.

Answer 1

Tại sao bạn muốn từ chối nó mà không sử dụng một ví dụ? Đó là cách trực tiếp nhất để bác bỏ khiếu nại.

Nếu bạn phải chứng minh điều đó thay vào đó, tất nhiên bạn sẽ không thể sử dụng một ví dụ. Trong trường hợp này, contrapositive có thể làm việc rất tốt - giả sử rằng yêu cầu là sai, và sau đó cho thấy cách dẫn đến một sự không thống nhất hợp lý.

Trong trường hợp này, bạn bắt đầu với f(n) <= c1 * g(n) là đúng, vì đây là ý nghĩa của f(n) = O(g(n)). Bây giờ bạn muốn giả định rằng g(n) <= c2 * f(n) là đúng cho tất cả f và g (phần cuối cùng này rất quan trọng, vì bạn chắc chắn có thể chọn f và g sao cho đúng) và hiển thị lý do tại sao điều này không thể hoạt động. Gợi ý của tôi cho bạn: chọn một số f và g sao cho nó không thể hoạt động và cho thấy rằng nó không thể hoạt động theo lựa chọn của bạn là c1 và c2.

Answer 2

Một vài gợi ý:
Đừng quên rằng f(n) = O(g(n)) là set notation và bạn có thể chuyển đổi nó thành dạng bất bình đẳng toán học.

hoạt động đơn giản bạn có thể làm với các O -notation:

• f(n) = O(f(n))
• c * O(f(n)) = O(f(n)), nếu c là hằng số
• O(f(n)) + O(f(n)) = O(f(n))
• O(O(f(n))) = O(f(n))
• O(f(n)) * O(g(n)) = O(f(n)g(n))
• O(f(n)g(n)) = f(n) * O(g(n))

(The Art of Computer Programming, vol 1 - O -Notation)