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

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

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

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