¿Cómo demuestro que $ 3x ^ 3 + 2x + 1 $ es $ \ omega (x \ cdot \ log x) $

Question

Estoy tratando de responder a esta pregunta: $ 3x ^ 3 + 2x + 1 $ es $ \ omega (x \ cdot \ log x) $

Mi pregunta es cómo resolver esta pregunta.

Aquí está lo que he intentado hasta ahora:

Aplicé la definición $ 3x ^ 3 + 2x + 1> C \ CDOT X \ LOG X $ para todos c, dados $ n \ geq k $ , para algunos k

Intenté aplicar la técnica de aplicar la igualdad que: $ n

Dado que n es menor que el término de orden más alto, podemos mover todos los términos a pedido n?

Donando $ 6x

entonces puedes elegir: $ k <2 ^ \ frac {6} {c} $

Answer 1

Lo que recomiendo primero es notar que si está buscando la complejidad de la función $ 3x ^ 2 + 2x + 1 $ , realmente todo lo que debe preocuparse es la función $ x ^ 2 $ . Porque si demostrará que $ x ^ 2=omega (xlogx) $ Luego, agregar el $ 2x + 1 $ no arruinará esa prueba desde $ x ^ 2 $ es polinomialmente más grande que $ 2x + 1 $ y por lo que podemos simplemente mirar el $ x ^ 2 $ . < / p>

(usaré $ n $ en lugar de $ x $ porque eso es lo que soy familiarizado con, pero es exactamente lo mismo para $ x $ )

Así que ahora lo que queremos probar es que $$ N ^ 2=OMEGA (NLOGN) $$

¿Cuál es lo que ofreció solo necesita para voltear sus lados en la ecuación, tendremos que encontrar un $ c $ , para que para cualquier clase $ N> n_0 $ o $ n> k $ : $$ f (n) \ ge c \ cdot g (n) $$ Cuándo $ f (n)= n ^ 2 $ , $ g (n)= nlogn $

que nos llevará a: $ n ^ 2 \ ge cnlogn $

Podemos dividir ambos lados por $ n $ : $$ N \ GE CLOGN $$

Ahora eso es un poco difícil. Pero "se sabe" que el tiempo de funcionamiento polinomial es más lento que lo logarítmico.

Básicamente, lo que significa es que prefiere alcanzar un tiempo de funcionamiento de la complejidad logarítmica si es posible, ya sea porque obtendrá una ejecución más rápida.

En general, este es el orden de los tiempos de ejecución cuando el primero es el más rápido:

$$ 1.Constant $$ $$ 2.Logarítmica $$ $$ 3.Linear $$ $$ 4. linealEarithmic $$ $$ 5.Polinomial $$ $$ 6.Exponential $$

(puede leer más al respecto aquí: https://adrianmejia.com/most-popular-algorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course/ )

Otra forma de verlo Es si encuentra el límite de la división de las dos funciones, digamos que elegiremos: $$ {f (n) \ sobre g (n)} $$

Si $$ \ lim_ {n \ to \ infty} {f (n) \ sobre g (n)} \ rudotrow \ infty $$ Significa que $ f (n) $ es "mucho más grande" que $ g (n) $ < / p>

Si $$ \ lim_ {n \ to \ infty} {f (n) \ sobre g (n)} \ rudotrow 0 $$ Significa que $ f (n) $ es "mucho más pequeño" que $ g (n) $ < / p>

La última opción (al menos en este método) es: $$ \ lim_ {n \ to \ infty} {f (n) \ sobre g (n)} \ rudowarrow C $$ Cuando $ c \ gt 0 $ lo que significa que ambas funciones tienen asintóticamente la misma complejidad.

Volver a nuestras funciones, podemos ver que: $$ \ lim_ {n \ to \ topty} {n \ a través de log (n)} $$

Usaremos la regla lupital y obtendremos: $$ \ lim_ {n \ to \ infty} {1 \ sobre 1 / n} \ rudowarrow \ infty $$

Ahora podemos ver que $ f (n)= n $ es mayor asintóticamente de $ g (n)= log (n) $ por lo tanto: $$ n=omega (log (n)) $$

---

Realmente espero que me explique lo más claro y más fácil posible, es solo que el inglés no es mi idioma de la lengua materna, por lo que apolegé de antemano por ningún error con Grammer, etc.

---

Actualización: He notado que ha realizado cambios en la función original y ahora es $ 3x ^ 3 + 2x + 1 $ , sin embargo, la prueba será Sé lo mismo, solo use $ n ^ 3 $ y de lo que aún obtendrá el mismo resultado al usar Lupital. Eso porque, inevitablemente, si solo probamos que $ n ^ 2 $ es mucho más grande que $ log (n) $ < / span> de lo que, por supuesto, que $ n ^ 3 $ que es mucho más grande que $ n ^ 2 $ también sería más grande que $ log (n). $

Answer 2

La forma más fácil es verificar que $ \ lim_ {x \ to \ infty} \ frac {3x ^ 3 + 2x +1} {x \ log x}= + \INFTY $ , que es una condición suficiente para $ 3x ^ 3 + 2x +1 \ in \ omega (x \ log x) $ .

$$ \ lim_ {x \ to \ infty} \ frac {3x ^ 3 + 2x +1} {x \ log x}= \ lim_ {x \ to \ infty} \ frac {3x ^ 3} {x \ log x}= \ lim_ {x \ to \ infty} \ frac {3x ^ 2} {\ log x}= \ lim_ {x \ to \ tyty} 6x ^ 2 = + \ INFTY. $$