تالار گفتمان مانشت

با درود
دوستان من حداقل ۱۵ مورد تمرین این جوری از کتاب لویستین حل کردم و خوب یاد گرفتم
اما سراغ این سوالات خودم رفتم. به نظرم خیلی سخت تر امد
اونجا مثلا n به توان 3 رو با n فاکتوریل قیاس میکرد و راه حلش مشخص بود اما اینجا نه
امکان داره کمکی کنید
اینها با اثبات ریاضی و قانع کننده باید مرتب کنم

سلام، کتاب لویتین خوبه ولی این موضوع در کتاب‌های کنکوری هم خوب بیان شده.
یک نگاهی به CLRS و حل تمرینش بیندازید بد نیست.

(11 فروردین 1395 02:22 ب.ظ)MShariati نوشته شده توسط: [ -> ]سلام، کتاب لویتین خوبه ولی این موضوع در کتاب‌های کنکوری هم خوب بیان شده.
یک نگاهی به CLRS و حل تمرینش بیندازید بد نیست.

بله اما همان جا هم تمرین های ساده حل کرده و تمرین های سخت مثل این گذاشته برای تمرین هایی که جواب ش هم نیست!

(11 فروردین 1395 11:44 ق.ظ)irpersian20 نوشته شده توسط: [ -> ]با درود
دوستان من حداقل ۱۵ مورد تمرین این جوری از کتاب لویستین حل کردم و خوب یاد گرفتم
اما سراغ این سوالات خودم رفتم. به نظرم خیلی سخت تر امد
اونجا مثلا n به توان ۳ رو با n فاکتوریل قیاس میکرد و راه حلش مشخص بود اما اینجا نه
امکان داره کمکی کنید
اینها با اثبات ریاضی و قانع کننده باید مرتب کنم

سلام.از همشون لگاریتم بگیرید.به سادگی مرتب میشن.
بطور کلی اگه بخوایم رشد f و g رو مقایسه کنیم،میتونیم از هر دو لگاریتم بگیریم،
اگه مثلا رشد لگاریتم f کمتر از رشد لگاریتم g بود،آنگاه میتونیم بگیم که رشد f هم کوچکتر مساوی رشد g هستش.
ولی اگه لگاریتم گرفتیم و رشد لگاریتم f و g یکسان شد،نمیتونیم نظری بدیم.

تو این سوال اگه از همشون لگاریتم بگیرید،ترتیب رشدشون مشخص میشه،غیر دو تابع [tex]\frac{n}{\lg n}\: \: \: ,\: \: \: \: \lg^2(n!)[/tex] که رشد لگاریتمشون برابره ولی کوچکتر از بقیه س. که اینم مشخصه که [tex]\: \lg^2(n!)[/tex] رشدش بیشتره،چونکه [tex]\: \lg^2(n!)\: \sim\: (\lg(n!))^2\: \: \sim\: \: (n\: lgn)^2\: \sim\: \: n^2\: \lg^2n[/tex] و این رشدش از [tex]\frac{n}{\lg n}[/tex] بیشتره.

پس اینم از جواب:
[tex]\frac{n}{\lg n}\: \: <\: \: \: \lg^2(n!)\: \: <\: \: \: (n^2)^{\lg n}\: \: \: <\: \: n^{\sqrt{n}}\: \: <\: \: \: \sqrt{n}^n\: \: \: <\: \: (\lg n)^{n^2}[/tex]

سلام ممنون
ببخشید این دو تا چطور با هم مقایسه میشه؟

(13 فروردین 1395 11:02 ق.ظ)irpersian20 نوشته شده توسط: [ -> ]سلام ممنون
ببخشید این دو تا چطور با هم مقایسه میشه؟

[tex]\lg(n^2)^{\lg n}\: \sim\: \lg n.\lg(n^2)\: \: \sim\: 2\lg n.\lg n\: \sim\: \: \lg^2n\: [/tex]

[tex]\lg(\lg n)^{n^2}\: \sim\: n^2\: \lg\lg n[/tex]

چون رشد لگاریتم دومی از رشد لگاریتم اولی بزرگتره،پس رشد لگاریتم دومی بزرگتر مساوی رشد لگاریتم اولی است:
[tex](n^2)^{\lg n}\: \epsilon\: O((\lg n)^{n^2})[/tex]

[tex](\lg n)^{n^2}\: \epsilon\: Omega\: ((n^2)^{\lg n})[/tex]