Notación Big Oh - definición formal

Question

Estoy leyendo un libro de texto en este momento para mi clase Java III. Estamos leyendo sobre Big-Oh y estoy un poco confundido por su definición formal.

Definición formal: "Una función f (n) es de orden como máximo g (n) - es decir, f (n) = O (g (n)) - si es un número real positivo cy entero positivo N existen tales que f (n) < = cg (n) para todo n> = N. Esto es, cg (n) es un límite superior en f (n) cuando n es suficientemente grande. "

Ok, eso tiene sentido. Pero espera, sigue leyendo el libro ... me dio este ejemplo:

"En el segmento 9.14, dijimos que un algoritmo que utiliza 5n + 3 operaciones es O (n) Ahora puede mostrar. que 5n + 3 = O (n) mediante el uso de la definición formal de grande Oh.

Cuando n> = 3, 5 n + 3 < = 5 n + n = 6 n. por lo tanto, si dejamos que f (n) = 5n + 3, g (n) = n, c = 6, N = 3, hemos demostrado que f (n) < = 6 g (n) para n> = 3, o 5n + 3 = O (n). Es decir, si un algoriti thm requiere tiempo directamente proporcional a 5n + 3, es O (n). "

Ok, este tipo de cosas tiene sentido para mí. Dicen que si n = 3 o más, 5n + 3 toma menos tiempo que si n fuera menor que 3, por lo tanto 5n + n = 6n - ¿no? Tiene sentido, ya que si n era 2, 5n + 3 = 13 mientras que 6n = 12, pero cuando n es 3 o más, 5n + 3 siempre será menor o igual que 6n.

Aquí es donde me confundo. me dan otro ejemplo:

Ejemplo 2: "Vamos a mostrar que 4n^2 + 50n - 10 = O (n^2) Es fácil ver que:. 4n^2 + 50n - 10 < = 4n^2 + 50n para cualquier n Desde 50n < = 50n^2 para n

= 50, 4n^2 + 50n -. 10 < = 4n^2 + 50n^2 = 54n^2 para n> = 50. Por lo tanto, con c = 54 y N = 50, hemos demostrado que 4n^2 + 50n - 10 = O (n^2). "

Esta afirmación no tiene sentido: 50n 50n < =^2 para n> = 50.

no hay ninguna n va a hacer el 50n menos de 50n^2? No solo mayor o igual a 50? ¿Por qué siquiera mencionaron que 50n < = 50n^2? ¿Qué tiene eso que ver con el problema?

Además, 4n^2 + 50n - 10 < = 4n^2 + 50n^2 = 54n^2 para n> = 50 va a ser cierto sin importar lo que sea n.

¿Y cómo los números de picking muestran que f (n) = O (g (n))?

Answer 1

Tenga en cuenta que está buscando "un límite superior en f (n) cuando n es suficientemente grande". Por lo tanto, si puede demostrar que f (n) es menor o igual que algunos c g (n) para valores de n mayores que N, esto significa que c g (n) es un límite superior para f (n) y La complejidad de f (n) es, por lo tanto, O (g (n)).

Los ejemplos dados tienen la intención de mostrar que la función dada f (n) nunca puede crecer más allá de c * g (n) para cualquier n> N. Manipulando un límite superior inicial para que pueda expresarse más simple (si 4n^2 + 50n es un límite superior en f (n) entonces también lo es 4n^2 + 50n^2, que es igual a 54n^2, que se convierte en su 54 * g (n) donde c = 54 yg (n) = n^2), los autores pueden demostrar que f (n) está limitada por c * g (n), que tiene complejidad O (g (n)) y por lo tanto también lo hace f (n).

Answer 2

50n <= 50n^2 for n >= 50 

porque si n es 50, entonces 50n es lo mismo que n^2, porque 50 * 50 es igual a 50^2.

Sustituyendo n^2 para 50n obtenemos

n^2 <= 50n^2 for n >= 50 

que es obvio.

Answer 3

Todo lo relacionado con la selección de números es simplemente esto: Para hacerlo más fácil. Debido a que puede elegir los números que desee para N y C, el autor simplemente elige algo, donde es más fácil de ver. Y eso es lo que también puedes hacer (al escribir un examen, etc.).

Por lo tanto, aunque a menudo sería posible usar una N más pequeña, el razonamiento sería un poco más difícil (a menudo requiere algún conocimiento previo sobre el análisis; todos hemos aprendido años antes, que x no crece tan rápido como x^2 ... Pero ¿quieres anotar la prueba de análisis?)

Mantenlo simple, es el mensaje :-) Es un poco extraño acostumbrarse a esto al principio.

Answer 4

Probablemente la razón por la que dijeron 50n < = 50n^2 para n> = 50 es que si n es menor que 1, entonces n^2 < n. Por supuesto, si n es un entero positivo, entonces sí 50n < = 50n^2. En este caso, parece que n se supone que es un entero positivo, aunque la definición formal que dan no lo establece explícitamente.

Puedo ver por qué decir 50n < = 50n^2 para n> = 50 puede parecer un poco tonto. Pero sigue siendo cierto. El libro no dice 50n < = 50n^2 tiene SÓLO para n> = 50; eso sería falso

Como analogía, si digo "todos mis hermanos hablan inglés", eso sería cierto, aunque hay muchas personas que hablan inglés que no son mis hermanos.

En cuanto a la prueba, podríamos dividirla en diferentes declaraciones.

(1): 4n^2 + 50n - 10 <= 4n^2 + 50n (for all n) 
(2): 4n^2 + 50n <= 4n^2 + 50n^2 (for all n>=50) 
(3): 4n^2 + 50n^2 = 54 n^2 (for all n, including all n>=50) 
(4): Therefore, 4n^2 + 50n - 10 <= 54n^2 for all n>=50 
(5): Therefore, for f(n)=4n^2 + 50n - 10, g(n)=n^2, N=50, and c=54, 
      the statement f(n) <= c g(n) for all n >= N is true 
(6): Therefore, by definition 4n^2 + 50n - 10=O(n^2). 

Debe quedar claro que cada una de estas afirmaciones es verdadera, ya sea por cuenta propia (1,2,3), o como resultado de las declaraciones anteriores.

Answer 5

definición formal:

• f (n) = O (g (n)) significa que no existir c> 0 y n tal que para cualquier n> = n f (n) < = c * g (n)
• f (n) = o (g (n)) medio para que cualquier c> 0 existen n tal que para cualquier n> = n f (n) < = c * g (n)

Como se puede notar hay un poco diferente :)