(۱۱ فروردین ۱۳۹۵ ۱۱:۴۴ ق.ظ)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]