dimostrare n = Big-O (1) usando induzione

Question

So che la relazione n = Big-O (1) è falsa. Ma se usiamo l'induzione che coinvolge Big-O può essere provato. Ma l'errore è che non possiamo indurre Big-O. Ma la mia domanda è come possiamo confutare la relazione usando le costanti.

La prova falsa è qui, per favore dammi la prova di essere falsi usando le costanti. Mi sto confondendo con le costanti, non so se ciascuna relazione utilizzata nella dimostrazione abbia una costante diversa o uguale. Per favore, illumina sull'argomento. ipotesi

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

induzione: lasciare che sia vero: n-1 = O (1) ora dimostriamo che n = O (1)

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

falsamente dimostrato .. voglio il chiarimento della fallacia in termini di < = e costanti, che è nella definizione di base di Big-O.

Answer 1

Una cosa che dovete capire qui è che Big-O o semplicemente O denota la "velocità" con cui una funzione cresce. Non è possibile utilizzare l'induzione matematica per provare questa particolare proprietà.

Un esempio è

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

Per la matematica semplice, la dichiarazione di cui sopra comporta O (n) = 0 che non lo è. Quindi direi di non usare l'MI per questo. MI è più appropriato per i valori assoluti.

Answer 2

La notazione O grande riguarda le funzioni, quindi affermazioni come 1 = O(1) non hanno alcun significato. Quello che stai dimostrando qui è che se si prende un arbitrario n e la funzione costante f(x) = n quindi f = O(1) che è vero e non dà alcuna contraddizione. Non c'è alcun problema con la dimostrazione, il problema è che si confonde la funzione costante f(x) = n con la funzione f(n) = n. Per quest'ultimo abbiamo quello f = O(n) e se provate a dimostrarlo con il vostro metodo vedrete che non funzionerà.

Answer 3

C'è un enorme errore logico nascosto qui:

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

n è una funzione e & Omicron; (1) è un insieme di funzioni. Né è un numero (e le prove di induzione servono a provare le cose per un intero gruppo di numeri individuali in un colpo solo). L'uso di segni di uguale, come n = & Omicron; (1), is an informal shorthand for f ∈ Ο(1), where f(x) = x.

Questa prova utilizza the fallacy of equivocation in due modi:

• facendo finta che n è un numero (il numero successivo nel viaggio induttivo), piuttosto che un intero funzione
• fingendo segno di uguaglianza significa che due numeri sono uguali, che è ciò che significa in una dimostrazione per induzione, invece di essere una scorciatoia per elemento di

Se volete vedere più chiaramente perché questa prova non riesce, sostituire n con un'altra notazione per una funzione, f (dove f (x) = x), e i segni di uguale con l'elemento-di segni dove necessario e vedere se la prova ha ancora senso.

Caso base:

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

caso induttivo:

 
      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] 

Diventa molto più chiaro che questa non è un'induzione prova a tutti. Non è nemmeno una prova valida a sé stante, perché abbiamo solo provato che h ∈ e Omicron; (1), che non ha nulla a che fare con g ∈ e Omicron; (1), poiché tali funzioni agiscono in modo molto, molto diverso l'una dall'altra .

Answer 4

Se è necessario eseguire prove rigorose con notazione Big-O, è necessario iniziare con format definition of Big-O In una dimostrazione non si può semplicemente dire O(1) + 1 = O(1). Devi fare la prova in termini di definizione formale. Per dimostrare che una funzione (f(n) = n per esempio) è O (1), è necessario trovare x0 e M univoci che corrispondano alla definizione. È possibile dimostrare questo attraverso l'induzione, e si può anche fare una dimostrazione per assurdo utilizzando la definizione di dimostrare che non è f(n) = nO(1)

Proprio come Olathe dichiarato nella sua risposta, non si può semplicemente aggiungere set di Big-O e funzioni. Inizia con la definizione formale di cosa classifica una funzione come membro di un particolare set Big-O.