D'essais et d'Infirmer BigO

À prouver et réfutation Big O questions explicitement de dire l'utilisation de la définition de prouver et de réfuter, ma question est, est ce que je suis en train de faire corriger?

Par exemple vous avez une question qui est g(n) = O(f(n)) ... pour le prouver, je faisais les suivantes

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

La contradiction que je lance quand faire, c'est lorsque je m'approche d'une question de réfutation de ce genre de choses

par exemple

g(n) =O(F(n)) pour la réfuter, je le ferais

g(n) >= C(F(n)) et les solutions de C à nouveau . Cependant, ce qui m'amène à croire que le big O peut être prouvé et démentie à la fois ? qui est 100% faux.

L'aide du monde réel numéros
(Prouver)

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)

ces deux dire que @ n =1 et c = 3 de l'algorithme est O(n^2) et n'est PAS en O(n^2).

Quelqu'un peut-il m'aider à clarifier ma confusion et de me donner une aide-moi à apprendre une bonne façon algorithmique de résolution de big O questions?

OriginalL'auteur Faisal Abid | 2010-02-11

  1. 11

    Ni de vos techniques de travail. Commençons par la définition de " big-O:

    f est O(g) ssi il existe C, N tel que |f(x)| ≤ C |g(x)| pour tout x ≥ N

    À prouver "il existe" les instructions de type, vous devez montrer que, eh bien, les choses existent. Dans le cas de big-O de preuves, vous trouverez généralement les choses, bien que les preuves de l'existence n'avez généralement pas besoin d'être constructif. Pour construire une preuve pour une "pour tous", de faire semblant de quelqu'un vous a remis des valeurs spécifiques. Attention vous faites pas de suppositions implicites au sujet de leurs propriétés (vous pouvez explicitement les propriétés de l'état, tels que le N > 0).

    Dans le cas de la preuve de big-O, vous devez trouver le C et N. Afficher |g(n)| ≤ C|F(n)| pour une seule n est pas suffisante.

    Pour l'exemple ", n2+3 est O(n2)":

     Pour n ≥ 2, on a: 
n2 ≥ 4 > 3 
⇒ n2-1 > 2 
⇒ 2(n2-1) > (n2-1)+2 
⇒ 2n2 > (n2-1)+4 = n2+3 
Ainsi, n2+3 est O(n2) pour C=2, N=2.

    Réfuter, vous prenez la négation de l'énoncé: il n'y ait pas C ou N. En d'autres termes, montrer que, pour tous les C et N, il existe un n > N tel que |f(n)| > C |g(n)|. Dans ce cas, le C et N sont qualifiés de "pour tous", afin de prétendre qu'ils ont été donnés. Depuis n est qualifiée de "il existe", vous devez le trouver. C'est là que vous commencez avec l'équation que vous souhaitez prouver et de travailler vers l'arrière jusqu'à ce que vous trouver un n.

    Supposons que nous voulons prouver que ce n est pas O(ln n). Faire semblant de nous est donnée de N et de C, et nous avons besoin de trouver un n ≥ N tel que n > C ln n. 

    Pour tous les nombres entiers de C, N, M=1+max(N, C) et n = eM. Remarque n > N > 0 et M > 0. 
Donc n = eM > M2 = M ln eM = M ln n > C ln n. CQFD.

    Preuves de x > 0 ⇒ ex > x2 et "n est pas O(ln n)" ⇒ "n est pas O(logb n)" de gauche " que des exercices.

    salut @outis, je sais que sa a été un moment depuis que vous avez posté la réponse mais je ne comprends pas votre preuve. Dans 'n^2-1 > 2" pourquoi avez-vous décidé de mettre le '-1'? parce que n^2 > 2. Comment avez-vous '2(n^2-1) > (n^2-1)+2' ? Je ne comprends pas la logique derrière elle. Aussi je ne comprends pas comment vous avez obtenu '2n^2 > (n^2-1)+4', pourquoi avez-vous déposez le (n^2-1) de la première partie de l'énoncé? comment avez-vous le 4 à la fin de l'instruction? J'ai un fort sentiment de ces simples questions, mais je ne peux vraiment pas comprendre. Faites-moi confiance, j'ai essayé. J'espère que vous allez répondre. Merci à l'avance.
    Chaque inégalité (autre que le premier) est dérivée de la précédente (d'où le "⇒"). Pour suivre, appliquer la norme d'algèbre règles, comme un "> b ⇒ a+c > b+c". La simplification des mesures ont été laissés de côté (donc, "+ ... " est écrit que "2a", plutôt que "a+a = 2a ...").

    OriginalL'auteur outis