f = n(log(n))^5
g = n^1.01
es
f = O(g)
f = 0(g)
f = Omega(g)?
Probé dividiendo tanto por n y me dieron
f = log(n)^5
g = n^0.01
Pero todavía estoy desorientado a la que uno crece más rápido. ¿Alguien puede ayudarme con esto y explicar el razonamiento de la respuesta? Realmente quiero saber cómo (sin calculadora) se puede determinar cuál crece más rápido.
Probablemente más fácil de comparar sus perfiles logarítmicos:
Si (para algunos C1, C2, a> 0)
f < C1 n log(n)^a
g < C2 n^(1+k)
Entonces (para n suficientemente grande)
log(f) < log(n) + a log(log(n)) + log(C1)
log(g) < log(n) + k log(n) + log(C2)
Tanto están dominados por el crecimiento de log (n), por lo que la pregunta es qué residuo es más grande. El log (n) residual crece más rápido que log (log (n)), independientemente de cuán pequeña es k o qué tan grande es a, por lo que g crecerá más rápido que f.
Así que en términos de la notación grande-O: g crece más rápido que f, por lo que f lata (asintóticamente) ser acotada superiormente por una función como g:
f(n) < C3 g(n)
Así f = O (g). Del mismo modo, g puede estar limitado desde abajo por f, por lo que g = Omega (f). Pero f no puede delimitarse desde abajo con una función como g, ya que g eventualmente la superará. Entonces f! = Omega (g) y f! = Theta (g).
Pero aaa hace un muy buen punto: g no comienza a dominar sobre f hasta que n se vuelve obscenamente grande.
No tengo mucha experiencia con la escala del algoritmo, por lo que las correcciones son bienvenidas.
¿qué tal verificar sus intersecciones?
Solve[Log[n] == n^(0.01/5), n]
1809
{{n -> 2.72374}, {n -> 8.70811861815 10 }}
hice trampa con Mathematica
que también puede razonar con derivados,
In[71]:= D[Log[n], n]
1
-
n
In[72]:= D[n^(0.01/5), n]
0.002
------
0.998
n
considerar lo que sucede a medida que n se hace muy grande, el cambio en la primera tiende a cero, después funcione doesnt perder su derivada (exponente es mayor que 0).
esto le dice que es más complejo teóricamente. Sin embargo, en la región práctica, la primera función va a crecer más rápido.
sí, eso es genial, pero no me gustaría tener eso en la prueba = ( – denniss
@den muchas veces las curvas tendrán un crecimiento "diferente" en los extremos. La manera rápida y sucia es solo tomar algunos puntos de muestra y determinar el crecimiento a partir de los valores muestreados. – Anycorn
estoy de acuerdo y eso es lo que haría si tuviera el recurso, pero muchas veces se espera que respondamos a estas preguntas sin la ayuda de ninguna electrónica. – denniss
Me gustaría romper este en varios lemas fáciles, reutilizables:
Lema 1: Para una constante positiva k, f = O (g) si y sólo si f = O (k g).
Prueba: Supongamos que f = O (g). Entonces existen constantes c y N tales que | f (n) | < c | g (n) | para n> N. Por lo tanto | f (n) | < (c/k) (k | g (n) |) para n> N y constante (c/k), entonces f = O (k g). Lo contrario es trivialmente similar.
Lema 2: Si h es una función monótonamente creciente positivo y f y g son positivos para n suficientemente grande, entonces f = O (g) si y sólo si h (f) = O (h (g)).
Prueba: Supongamos que f = O (g). Entonces existen constantes c y N tales que | f (n) | < c | g (n) | para n> N. Dado que f y g son positivos para n> M, f (n) < c g (n) para n> max (N, M). Como h es monótonamente creciente, h (f (n)) < c h (g (n)) para n> max (N, M), y por último | h (f (n)) | < c | h (g (n)) | para n> max (N, M) ya que h es positivo. Por lo tanto h (f) = O (h (g)). Lo contrario sigue de manera similar; el hecho clave es que si h es monótonamente creciente, entonces h (a) < h (b) => a < b.
Lema 3: Si h es un invertible función monótona creciente, entonces f = O (g) si y sólo si f (h) + O (g (h)).
Prueba: Supongamos que f = O (g). Entonces existen constantes c, N tales que | f (n) | < c | g (n) | para n> N. Entonces | f (h (n)) | < c | g (h (n)) | para h (n)> N. Dado que h (n) es invertible y monótonamente creciente, h (n)> N siempre que n> h^-1 (N). Así h^-1 (N) es la nueva constante que necesitamos, y f (h (n)) = O (g (h (n)). Lo contrario sigue de manera similar, usando inversa de g.
Lema 4: Si h (n) es distinto de cero para n> M, f = O (g) si y solo si f (n) h (n) = O (g (n) h (n)).
Prueba: si f = O (g), entonces para las constantes c, N, | f (n) | < c | g (n) | para n> N. Dado que | h (n) | es positivo para n> M , | f (n) h (n) | < c | g (n) h (n) | para n> max (N, M) y tan f (n) h (n) = O (g (n) h (n)). Lo contrario se sigue de manera similar usando 1/h (n).
Lemma 5a: log n = O (n).
Prueba: Let f = log n, g = n. Entonces f '= 1/n y g' = 1, entonces para n> 1, g aumenta más rápidamente que f. Además g (1) = 1> 0 = f (1), entonces | f (n) | < | g (n) | para n> 1 yf = O (g).
Lemma 5b: n! = O (log n).
Prueba: Supongamos lo contrario por contradicción, y sea f = n y g = log n. Luego, para algunas constantes c, N, | n | < c | log n | para n> N.
Sea d = max (2, 2c, sqrt (N + 1)). Por el cálculo en el lema 5a, desde d> 2> 1, log d < d. Por lo tanto | f (2d^2) | = 2d^2> 2d (log d)> = d log d + d log 2 = d (log 2d)> 2c log 2d> c log (2d^2) = cg (2d^2) = c | g (2d^2) | para 2d^2> N, una contradicción. Por lo tanto f! = O (g).
Así que ahora podemos armar la respuesta a la pregunta que hizo originalmente.
Paso 1:
log n = O(n^a)
n^a != O(log n)
Para cualquier constante positiva a.
Prueba: log n = O (n) por Lemma 5a. Por lo tanto, log n = 1/a log n^a = O (1/an^a) = O (n^a) por Lemmas 3 (para h (n) = n^a), 4 y 1. El segundo hecho sigue de manera similar al usar el Lema 5b.
Paso 2:
log^5 n = O(n^0.01)
n^0.01 != O(log^5 n)
Prueba: log n = O (n^0.002) mediante la etapa 1. A continuación por el Lema 2 (con h (n) = n^5), log^5 n = O ((n^0.002)^5) = O (n^0.01). El segundo hecho sigue de manera similar.
respuesta final:
n log^5 n = O(n^1.01)
n^1.01 != O(n log^5 n)
En otras palabras,
f = O(g)
f != 0(g)
f != Omega(g)
Prueba: Aplicar Lemma 4 (usando h (n) = n) al paso 2.
Con la práctica estos las reglas se vuelven "obvias" y la segunda naturaleza. y a menos que tu prueba requiera que demuestres tu respuesta, te encontrarás azotando a través de este tipo de problemas de gran O.
n = O (log n) significa que n puede estar limitado por un registro (n), pero seguramente eso no puede ser cierto desde n crece más rápido que log (n). El uso de O() parece ser lo opuesto a cómo lo he usado. ¿Estoy malinterpretando la notación? –
No, me equivoqué cuando escribí esa segunda parte de la publicación. Debería ser arreglado ahora. – user168715
Mientras que el Lema 1 puede ser matemáticamente sólido, lo adelgazo pone el énfasis en lo incorrecto. Parece sugerir que necesitas pensar en ambas cosas y que la primera parte es verdadera y de alguna manera está conectada a la segunda parte. Por supuesto, hay una conexión, pero la parte 'f = O (g)' es una cuestión de definición. Prefiero mostrar que 'f = O (k g)' se deduce del primero, eso parece mucho más intuitivo. – phant0m
Esto no es 100% matemáticamente kosher sin probar algo acerca de los registros, pero aquí va:
f = log(n)^5
g = n^0.01
Tomamos registros de ambos:
log(f) = log(log(n)^5)) = 5*log(log(n)) = O(log(log(n)))
log(g) = log(n^0.01) = 0.01*log(n) = O(log(n))
De esto vemos que el primero crece de manera asintótica más lenta, porque tiene un doble inicio de sesión y los registros crecen lentamente. Un argumento no formal sobre por qué este razonamiento al tomar registros es válido es el siguiente: log (n) le dice aproximadamente cuántos dígitos hay en el número n. Por lo tanto, si el número de dígitos de g crece de manera tan súbitamente más rápida que el número de dígitos de f, entonces seguramente el número real g está creciendo más rápido que el número f.
Este * puede * ser más adecuado para http://mathoverflow.net/. –
Probablemente demasiado elemental para mathoverflow. – user168715
@Space_COwbOy ¡Esto no es apropiado para mathoverflow.net! Eso es para matemáticos de investigación que realizan trabajos originales. http://math.stackexchange.com es el camino a seguir aquí. – aaronasterling