سلام.
کدام تابع به طور مجانبی بزرگتر است [tex]lg(lg^{*}n)[/tex] یا [tex]lg^{*}(lgn)[/tex] ؟ چرا؟
پیشاپیش از کمکتون ممنون.
(۳۱ شهریور ۱۳۹۱ ۰۵:۵۱ ب.ظ)mohabati10 نوشته شده توسط: سلام.
کدام تابع به طور مجانبی بزرگتر است [tex]lg(lg^{*}n)[/tex] یا [tex]lg^{*}(lgn)[/tex] ؟ چرا؟
پیشاپیش از کمکتون ممنون.
سلام
lg*n=lg*lgn+1
درنتیجهlg*n وlg*lgn هم درجه هستند، و میدانیم
lg n=o(n) .1
در نتیجه داریم
lg lg*n=o(lg*n) .2
و چون lg*n و lg*lgn هم درجه هستند، نتیجه میگیریم
lg lg*n=o(lg* lgn) .3
[tex]n=2^z,z=Lg(n),Lg^*(n)=lg^*(lg{(n)}) 1[/tex]
[tex]= lg^*(z*lg{(2)}) 1=lg^*(z*1) 1=lg^*(z) 1\Rightarrow Lg^*(n)=1 Lg^*(Lg(n))[/tex]
فقط این نکته رو در نظر داشته باشید که فرمول فوق در مورد مبنای ۲ بیشتر بکار می ره و در مبناهای دیگه ممکنه یکم پیچیده بشه و باید کران بالا رو حساب کنیم و با ۱ جمع کنیم.
ضمنا ، زیاد وارد این مباحث نشو چون مربطو به کنکور نیست.
و شما فقط مثال زیر را درک کنید برای کنکور کافیه :
Log*n یعنی تعداد لگاریتمی که باید از n بگیریم تا جواب تقریبا ۱ بشه.
مثال : Lg*16=3
زیرا:
lg16=4
lg4=2
lg2=1
دیدیم که سه بار از حاصل،لگاریتم گرفتیم تا جواب ۱ شد.
ضمنا دقت کن معمولا توی کتب ساختمان داده ها هرجا بنویسه Lg منظورش لگاریتم در مبنای ۲ هست.
(دقت کنید بعضی جاها lg رو با log اشتباه نکنید که ممکنه حتی بعضی کتابا هم اشتباهات ریز رو شامل بشن ،که خودتون باید هوشیار باشید)
==
اینم توضیحات دیگه :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
==
هرجا اشتباه کردم سریعا بهم تذکر بدید