Ayuda con notación O grande

Question

He estado teniendo problemas tratando de entender el concepto de notación O grande. Entonces, por definición, la O grande es la siguiente, T(n) ∈ O(G(n)) if T(n) <= G(n) * C.

Dado que la constante "C" puede ser cualquier número entero> 0, ¿no sería este el siguiente ejemplo también cierto?

Ejemplo:

n log n ∈ O(log n) 
n log n <= log n * c 

donde C es igual al valor de n.

Sé que la respuesta es n log n ∉ O(log n) pero no entiendo cómo C puede ser constante.

Gracias de antemano por su ayuda: D

Answer 1

c es sólo eso, una constante . Esto significa que no puede decir "deje c ser el valor de n", porque debe elegir alguna c primero y luego permitir que la comparación se mantenga para todos los n.

En otras palabras, para que un T (n) sea O (G (n)), debe existir no constante c tal que G (n) * c es mayor que T (n) para todo n.

Por lo tanto n log n no es O (log n) porque, independientemente de la constante que elija, n> c hará que n log n sea mayor que c log n.

Answer 2

Déjame repetir tus palabras.

c puede ser cualquier constante.

Esto significa que c no puede depender de n.

Answer 3

la idea es que la desigualdad se cumple para cualquier n y fijo c. así que, si bien puede encontrar una cierta c tal que n log n < c log n, (es decir, cualquier c> n), puede encontrar fácilmente otra n 'para la que no es válida (es decir, n'> c).

Answer 4

En la definición, debe determinar C solo por el T y G. Esto es lo que significa una constante C Entonces C no debería depender de la entrada de ellos. Por lo tanto, no puede considerar C = n

Answer 5

en la expresión n log n, no puede comparar el n externo con C, como lo está haciendo. Eso sería como tomar la expresión algrebraica x (x + 1) y reemplazar una de las x con una constante.

En n log n, n es una variable. En la gran expresión de O, C es una constante.

Answer 6

El valor de n depende de la configuración de entrada, el valor de C es fijo.

Entonces sí, si n = 16 y C = 256, parece que n^2 * lg (n) para un pequeño conjunto de entrada. Ahora aumente la entrada configurada en 100,000,000; el valor de C permanece en 256, ahora tiene 256 * lg (100,000,000)

Answer 7

Primero que nada, si n = C, entonces C no es una constante. Y en la mayoría de los algoritmos del mundo real, C es pequeño, por lo que la parte de la O grande suele dominar para los valores típicos de n.

Pero la complejidad de big-O se refiere a la eficacia de un algoritmo para n grande, especialmente cuando n se aproxima al infinito. En otras palabras, le dice la escalabilidad de un algoritmo: qué tan bien maneja un algoritmo dado una carga de trabajo muy grande o duplicada.

Si sabes que n es siempre pequeño, entonces la complejidad de la gran O no es tan importante, sino que debes enfocarte en el tiempo del reloj de pared requerido por el algoritmo. Además, si elige entre dos algoritmos que tienen la misma complejidad de O grande (por ejemplo, O (n log n)), con frecuencia uno es mejor que el otro (por ejemplo, la ordenación aleatoria de pivote generalmente supera una clasificación de montón binario).

Answer 8

Cada vez que estoy atascado en grande-oh, me parece útil pensar en ello como una competencia: Elijo una función Big-oh (por lo tanto, en su caso, logn) y una constante (c). Lo importante es que tengo que elegir un valor real. Generalmente elijo mil, solo porque. Luego, tengo que dejar que mi archienemigo seleccione cualquiera que elija. Por lo general, elige mil millones.

Luego hago la comparación.

Para terminar el ejemplo, 10^9 * (log (10^9)) ahora se hace claramente mucho más grande que 1000log (10^9). Por lo tanto, sé que el Big-oh no funcionará.

Answer 9

Creo que este enlace puede aclarar las cosas para usted.

http://mohalgorithmsorbit.blogspot.com/2013/12/complexity-theory-approaching.html