كيف أثبت أن $3x^3 +2x + 1 دولار $\omega(x \cdot \log x) $

Question

أنا أحاول الإجابة على هذا السؤال:$3x^3 +2x + 1$ هو $ \omega(x \cdot \log x)$

سؤالي هو كيفية حل هذا السؤال.

هنا هو ما كنت قد حاولت حتى الآن:

أنا طبقت تعريف $3x^3 + 2x + 1 > c \cdot x\log x$ لجميع ج ، نظرا $n \geq k$, بعض ك

حاولت تطبيق تقنية تطبيق المساواة:$n < ن^3$

منذ n أقل من أعلى مستوى المصطلح يمكننا نقل كافة الشروط من أجل n ؟ ؟

إعطاء $6x < ج \cdot x \log x$

ثم يمكنك اختيار:$k < 2^\فارك{6}{c}$

Answer 1

ما أوصي الأول هو لاحظ أنه إذا كنت تبحث عن تعقيد وظيفة $3x^2+2x+1$, حقا كل ما يجب أن تهتم به هو وظيفة $x^2$.لأن إذا سوف تثبت ذلك $x^2 = \omega(xlogx)$ ثم إضافة $2x + 1$ لن تدمر هذا دليل على منذ $x^2$ هو polynomially أكبر من $2x + 1$ ولذا فإننا يمكن أن مجرد إلقاء نظرة على $x^2$.

(سوف تستخدم $n$ بدلا من $x$ لأن هذا هو ما أنا على دراية ولكن هذا هو بالضبط نفس الشيء $x$)

حتى الآن ما نريد أن تثبت أن $$n^2 = \omega(nlogn)$$

التي عرضت فقط تحتاج إلى الوجه الجانبين في المعادلة, سوف تحتاج إلى العثور على الإيجابية $C$, حتى أن أي $n>n_0$ أو $n>k$ : $$f(n)\قه ج\cdot غرام(ن)$$ عندما $f(n) = n^2$ , $g(n) = nlogn$

التي سوف تحصل لنا:$n^2 \قه Cnlogn $

يمكننا تقسيم كل جانب $n$: $$n \قه Clogn$$

الآن هذا هو قليلا من واحد صعب.ولكن "فمن المعروف" أن الحدود وقت تشغيل أبطأ من لوغاريتمي واحد.

أساسا ما يعنيه ذلك هو أن كنت تفضل الوصول إلى لوغاريتمي تعقيد إدارة الوقت إذا كان ذلك ممكنا لأن من سوف تحصل على أسرع التنفيذ.

عموما هذا هو أمر تشغيل أوقات الأول هو الأسرع:

$$1.المستمر$$ $$2.لوغاريتمي$$ $$3.الخطية$$ $$4.Linearithmic$$ $$5.متعدد الحدود$$ $$6.أسي$$

(يمكنك قراءة المزيد عن ذلك هنا: https://adrianmejia.com/most-popular-algorithms-time-complexity-every-programmer-should-know-free-online-tutorial-course/)

طريقة أخرى لمعرفة إذا ستجد الحد من تقسيم وظائف اثنين ، دعونا نقول نحن سوف نختار:$${f(n) \على g(n)}$$

إذا $$\lim_{n o \infty} {f(n) \على g(n)} ightarrow \infty$$ فهذا يعني أن $f(n)$ هو "أكبر بكثير" مما $g(n)$

إذا $$\lim_{n o \infty} {f(n) \على g(n)} ightarrow 0$$ فهذا يعني أن $f(n)$ هو "أقل بكثير" من $g(n)$

الخيار الأخير (على الأقل في هذا الأسلوب) هو:$$\lim_{n o \infty} {f(n) \على g(n)} ightarrow C$$ عندما $ج \gt 0$ وهو ما يعني أن كلا من وظائف مقارب نفس التعقيد.

العودة إلى وظائف ، يمكننا أن نرى أن :$$\lim_{n o \infty} {n \على log(n)}$$

سوف نستخدم lupital القاعدة والحصول على:$$\lim_{n o \infty} {1 \1/n} ightarrow \infty$$

ونحن الآن يمكن أن نرى أن $f(n) = n$ هو أكبر مقارب من $g(n) = log(n)$ ومن ثم :$$n = \omega (log(n))$$

---

أتمنى شرح واضح وسهل ممكن انها مجرد الإنجليزية ليست لغتي الأم اللغة لذا apolegize مقدما عن أي أخطاء مع نحوي.... الخ

---

تحديث :لقد لاحظت أنك قد إجراء تغييرات على وظيفة الأصلي والآن هو $3x^3+2x+1$, بعد إثبات نفسه فقط استخدام $n^3$ و مما كنت سوف لا يزال الحصول على نفس النتيجة عند استخدام lupital.ذلك لأنه حتما ، إذا ثبت أن $n^2$ هو أكبر بكثير من $log(n)$ من بالطبع أن $n^3$ والتي هي أكبر بكثير من $n^2$ من شأنه أيضا أن تكون أكبر من $log(n).$

Answer 2

أسهل طريقة هو التحقق من ذلك $ \ lim_ {x \ to \ {frac {3x ^ 3 + 2x +1} {x \ log}= + \INFTY $ ، وهو شرط كاف ل 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 \ infty} 6x ^ 2 = + \ infty.