۰
subtitle
ارسال: #۱
  
سوال از CLRS
سلام.
کدام تابع به طور مجانبی بزرگتر است [tex]lg(lg^{*}n)[/tex] یا [tex]lg^{*}(lgn)[/tex] ؟ چرا؟
پیشاپیش از کمکتون ممنون.
کدام تابع به طور مجانبی بزرگتر است [tex]lg(lg^{*}n)[/tex] یا [tex]lg^{*}(lgn)[/tex] ؟ چرا؟
پیشاپیش از کمکتون ممنون.
۰
ارسال: #۲
  
RE: سوال از CLRS
(۳۱ شهریور ۱۳۹۱ ۰۵:۵۱ ب.ظ)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
۰
ارسال: #۳
  
سوال از CLRS
[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 اشتباه نکنید که ممکنه حتی بعضی کتابا هم اشتباهات ریز رو شامل بشن ،که خودتون باید هوشیار باشید)
==
اینم توضیحات دیگه :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
==
هرجا اشتباه کردم سریعا بهم تذکر بدید
[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 اشتباه نکنید که ممکنه حتی بعضی کتابا هم اشتباهات ریز رو شامل بشن ،که خودتون باید هوشیار باشید)
==
اینم توضیحات دیگه :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
==
هرجا اشتباه کردم سریعا بهم تذکر بدید
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close