(۲۴ آبان ۱۳۹۵ ۰۴:۴۹ ب.ظ)Pure Liveliness نوشته شده توسط:  

(24 آبان ۱۳۹۵ ۰۳:۵۷ ب.ظ)maneshti نوشته شده توسط:  سلام
من می خواستم رشد $n.2^n$ و $4^n$ رو مقایسه کنم.
رشد ۴ بتوان n بیشتره دیگه درسته؟
خوب.اومدم گفتم از حد استفاده کنم $\lim(\frac{n.2^n}{4^n})$ رو حساب کنم ۰ میشه درسته . پس رشد ۴ بتوان n بیشتره.

حالا فرض کنیم میومدم از ۲ تابع lg می گرفتم lg هارو مقایسه می کردم ببینم کدوم بیشتره.خوب پس باید n+lgn رو با ۲n مقایسه می کردم. ظاهری مشخصه که ۲n>n+lgn پس بازم مشخصه که رشد ۴ بتوان n بیشتره.

حالا فرضا ظاهری نمیشد قضاوت کرد:
اومدم حد گرفتم $\lim(\frac{n+\lg n}{2n})$ حاصل حد مشکل ایجاد میکرد wolframalpha جواب ۱/۲ رو داد خوب اگر این جواب درسته پس این ۲ تابع lg هاشون هم مرتبه است .پس خودشون هم هم مرتبه هستند؟ در صورتیکه اینظور نیست. آیا lg گرفتن بعد برای مقایسه lg ها حد گرفتن کار غلطیه؟ سرراست نیست ولی آیا غلطه؟

مشکلات استنتاج من رو بفرمایید.
ممنون

لگاریتم‌ها رو درست گرفتید
$\lg(4^n)=nlg(4)=2n$
$\lg(n\cdot2^n)=\lg(n)+\lg(2^n)=\lg n+nlg2=\lg n+n$
ولی وقتی لگاریتم و سپس حد گرفتید، اگه حدشون مساوی با ۱ نبود، اون موقع اونی که بیشتر هست، مرتبه‌ش هم بیشتره. مثلاً از توابع $f_1=n^2$ و $f_2=n$ لگاریتم و سپس حد بگیرید، میشه $\frac{\lg(f_1)}{\lg(f_2)}=\frac{2\lg n}{\lg n}=2\:$ یعنی حدشون عدد ثابت شد در حالی که مرتبه‌ی اولی مسلماً بیشتر بود. پس اون عددی که رسیدید بهش، نشون میده که تابعی که در مخرج کسر هست رو به چه توانی برسونید تا بشه تابع بالای کسر. این عدد اگه ۱ نبود، پس مرتبه‌شون برابر نیست. در حالت کلی:
$\frac{\lg(f_1)}{\lg(f_2)}=k\: \longrightarrow\: \lg(f_1)=klg(f_2)\: \longrightarrow\: 2^{\lg(f_1)}=2^{klg(f_2)}=(2^{\lg(f_2)})^k\: \longrightarrow\: f_1=f_2^k$