Probar y rechazar BigO

Question

Al probar y refutar las preguntas de Big O que explícitamente dicen usar la definición para probar y refutar, mi pregunta es, ¿lo que estoy haciendo es correcto?

Por ejemplo, usted tiene una pregunta que es g (n) = O (f (n)) ... Con el fin de demostrar que yo estaba haciendo lo siguiente

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

La contradicción que corro a cuando se hace esto es cuando me acerco a una pregunta de refutar esta materia

por ejemplo

g (n) = O (f (n)) para refutar lo que haría

g (n)> = C (F (n)) y resuelve C nuevamente. Sin embargo, ¿esto me lleva a creer que el gran O puede ser probado y refutado a la vez? que es 100% incorrecto

El uso de números reales (Demostrando)

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) 

Ambas dicen que @ n = 1 y c = 3 el algoritmo es O (n^2) y no es O (n^2) .

¿Alguien me puede ayudar a aclarar mi confusión y ayudarme a aprender una buena forma algorítmica de resolver grandes preguntas de O?

Answer 1

Ninguna de sus técnicas funciona. Comencemos con la definición de big-O:

f es O (g) si hay C, N tal que | f (x) | ≤ C | g (x) | para todo x ≥ N

Para probar "existen" declaraciones de tipo, es necesario demostrar que, además, se dan las cosas. En el caso de las pruebas de gran O, generalmente se encuentran las cosas, aunque las pruebas de existencia generalmente no necesitan ser constructive. Para crear una prueba para una afirmación "para todos", imagine que alguien acaba de entregarle valores específicos. Tenga cuidado de no hacer suposiciones implícitas sobre sus propiedades (puede indicar propiedades explícitamente, como N > 0).

En el caso de la prueba de orden O, es necesario encontrar el C y N . Mostrando | g (n) | ≤ C | F (n) | para una sola n no es suficiente.

Para el ejemplo "n 3 es O (n 2 )":

 
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. 

de refutar, se toma la negación de la declaración: mostrar que no hay C oN. En otras palabras, demuestre que para todos C y N, existe una n > N tal que | f (n) | > C | g (n) |. En este caso, el C y N están calificados "para todos", así que pretenda que se le han entregado. Como n está calificado como "existe", debe encontrarlo.Aquí es donde comienza con la ecuación que desea probar y trabaja hacia atrás hasta que encuentre un adecuado.

Supongamos que queremos demostrar que n no es O (ln n). Supongamos que nos dan N y C, y necesitamos encontrar un n ≥ N tal que 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. 

Las pruebas de x e ^x > x y "n no es O (ln n)" ⇒ "n no es O (log _b n)" izquierda como ejercicios .