chứng minh n = Big-O (1) sử dụng cảm ứng

Question

Tôi biết rằng quan hệ n = Big-O (1) là sai. Nhưng nếu chúng ta sử dụng cảm ứng liên quan đến Big-O nó có thể được chứng minh. Nhưng sai lầm là chúng ta không thể cảm ứng Big-O. Nhưng câu hỏi của tôi là làm thế nào chúng ta có thể bác bỏ mối quan hệ bằng cách sử dụng các hằng số.

Bằng chứng giả mạo ở đây, vui lòng cho tôi bằng chứng về việc đó là sai bằng cách sử dụng các hằng số. Tôi đang nhầm lẫn với các hằng số, tôi không biết liệu mỗi mối quan hệ được sử dụng trong các bằng chứng là có hằng số khác nhau hay giống nhau. Hãy khai sáng về chủ đề này.

TO prove: n= O(1) 
for n=1 , 1= O(1) proved 

cảm ứng giả thuyết: để cho nó là đúng: n-1 = O (1) bây giờ chúng tôi chứng minh rằng n = O (1)

LHS : n = (n-1) + 1 
     = O(1) + 1 
     = O(1) + O(1) 
     = O(1) 

tin bịa đặt chứng minh .. Tôi muốn làm rõ của sai lầm về mặt số < = và hằng số, đó là định nghĩa cơ bản của Big-O.

Answer 1

Một điều bạn phải hiểu ở đây là Big-O hoặc O đơn giản biểu thị 'tốc độ' mà tại đó hàm phát triển. Bạn không thể sử dụng cảm ứng Toán học để chứng minh tài sản cụ thể này.

Một ví dụ là

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

Bằng toán học đơn giản, tuyên bố trên ngụ ý O (n) = 0 mà không phải là. Vì vậy, tôi sẽ nói không sử dụng MI cho việc này. MI phù hợp hơn cho các giá trị tuyệt đối.

Answer 2

Ký hiệu O lớn là về các hàm, do đó, các câu lệnh như 1 = O(1) không có ý nghĩa. Những gì bạn đang chứng minh ở đây là nếu bạn có một tùy ý n và chức năng liên tục f(x) = n thì f = O(1) đúng và không có mâu thuẫn. Không có vấn đề với bằng chứng, vấn đề là bạn đang bối rối hàm hằng số f(x) = n với hàm f(n) = n. Đối với sau này chúng tôi có rằng f = O(n) và nếu bạn cố gắng để chứng minh nó với phương pháp của bạn, bạn sẽ thấy rằng nó sẽ không hoạt động.

Answer 3

Có một sai lầm logic khổng lồ ẩn ở đây:

 
LHS : n = (n-1) + 1 
     = O(1) + 1 
     = O(1) + O(1) 
     = O(1) 

n là một chức năng và & Omicron; (1) là một tập hợp các chức năng. Không phải là một số (và chứng minh cảm ứng là tất cả về việc chứng minh mọi thứ cho một bó toàn bộ số cá nhân trong một ngã swoop). Sử dụng các dấu bằng, như n = & Omicron; (1), is an informal shorthand for f ∈ Ο(1), where f(x) = x.

bằng chứng này sử dụng the fallacy of equivocation theo hai cách:

• bằng cách giả vờ rằng n là một số (số tiếp theo trong cuộc hành trình quy nạp) chứ không phải là toàn bộ chức năng
• bằng cách giả vờ những dấu hiệu bình đẳng có nghĩa là hai các con số bằng nhau, đó là ý nghĩa của nó trong một bằng chứng cảm ứng, thay vì viết tắt cho phần tử của

Nếu bạn muốn thấy rõ hơn tại sao bằng chứng này không thành công, thay thế n bằng ký pháp khác cho hàm, f (trong đó f (x) = x), và các dấu hiệu tương đương với các dấu hiệu yếu tố khi cần và xem liệu bằng chứng vẫn có ý nghĩa hay không.

trường hợp cơ sở:

 
let h(x) = 1 in 
      h ∈ Ο(1)  [Any function is in Ο(that function)] 

Inductive trường hợp:

 
      n = (n - 1) + 1 [Algebraic identity] 
     n - 1 = n - 1  [Arithmetic] 

let f(x) = x 
    g(x) = f(x) - 1 in 
      g ∈ Ο(1)  [Assume g ∈ Ο(1) because a different function, h, was] 
      f ∈ Ο(1 + 1) [By definition of Ο] 
      f ∈ Ο(2)  [Arithmetic] 

Nó trở thành rõ ràng hơn nhiều rằng đây không phải là một cảm ứng bằng chứng gì cả. Nó thậm chí không phải là bằng chứng hợp lệ theo đúng nghĩa của nó, bởi vì chúng tôi chỉ chứng minh rằng h ∈ & Omicron; (1), không liên quan gì đến việc g ∈ & Omicron; (1), vì những chức năng này hoạt động rất, rất khác nhau .

Answer 4

Nếu bạn cần thực hiện bất kỳ bằng chứng nghiêm ngặt nào liên quan đến ký hiệu Big-O, bạn cần phải bắt đầu bằng format definition of Big-O Trong bằng chứng bạn không thể chỉ nói O(1) + 1 = O(1). Bạn cần phải làm bằng chứng về định nghĩa chính thức. Để chứng minh rằng một hàm (ví dụ: f(n) = n) là O (1), bạn cần tìm duy nhất x0 và M khớp với định nghĩa. Bạn có thể chứng minh điều này thông qua cảm ứng, và bạn cũng có thể làm một bằng chứng của sự mâu thuẫn bằng cách sử dụng định nghĩa để chứng minh rằng f(n) = n không phải là O(1)

Cũng như Olathe tuyên bố trong câu trả lời của mình, bạn không thể chỉ cần thêm bộ Big-O và chức năng. Bắt đầu với định nghĩa chính thức về những gì phân loại một hàm như là một thành viên của một tập Big-O cụ thể.