چرا [tex]Lg(n!)= \Omega (nlgn)[/tex]
??!
[tex]\underbrace{\frac{n}{2}\times \frac{n}{2} \times \cdots \times \frac{n}{2}}_{\frac{n}{2}}\leq \underbrace{(\frac{n}{2} 1)\times (\frac{n}{2} 2) \times \cdots \times (\frac{n}{2} n)}_{\frac{n}{2}}\leq 1 \times 2 \times 3 \times \cdots \times n \Rightarrow {(\frac{n}{2})}^{\frac{n}{2}} \leq n! \Rightarrow \lg {(\frac{n}{2})}^{\frac{n}{2}} \leq \lg n![/tex]
حالا با توجه به اینکه داریم [tex]\lg {(\frac{n}{2})}^{\frac{n}{2}} = \Theta(n\lg n)[/tex] پس میشه گفت [tex]n\lg n \leq \lg {(\frac{n}{2})}^{\frac{n}{2}}[/tex]
با توجه به [tex]n\lg n \leq \lg {(\frac{n}{2})}^{\frac{n}{2}}[/tex] و همچنین [tex]\lg {(\frac{n}{2})}^{\frac{n}{2}} \leq \lg n![/tex] میشه نتیجه گرفت که [tex]n\lg n \leq \lg n![/tex] و این یعنی [tex]\lg n! = \Omega (n\lg n)[/tex]
ویرایش: یه اشتباهی کرده بودم. تو خط اول تعداد جملات باید n/2 باشه که من نوشته بودم n. تصحیح شد.
ممنون بابت جوابتون. من خط اول رو نفهمیدم! چجوری عبارت وسط از n! کمتر شد؟
یه جواب که برای این مسئله پیدا کردم این هست :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
به نظر بنده جواب دوستمون درست نیست دوستان به لینکی که بنده دادم مراجعه کنید تا دچار اشتباه نشوید.
یادمه یه جای مانشت این مسئله بررسی شده بود می تونید یه بررسی بفرمایید. جواب آقای mfXpert رو نمی دونم درست هست یا نه چون خیلی روش پیچیده ای بررسی کردن اما اینو بگم که ایشون از بهترین های مانشت در زمینه طراحی الگوریتم هستن
(27 دى 1391 11:17 ب.ظ)Masoud05 نوشته شده توسط: [ -> ]یادمه یه جای مانشت این مسئله بررسی شده بود می تونید یه بررسی بفرمایید. جواب آقای mfXpert رو نمی دونم درست هست یا نه چون خیلی روش پیچیده ای بررسی کردن اما اینو بگم که ایشون از بهترین های مانشت در زمینه طراحی الگوریتم هستن
سلام دوست عزیز
جواب mfXpert درسته؟
[tex]n!=n*(n-1)*(n-2)*....*2*1[/tex]
[tex]n! \geq (n/2)^{(n/2)}[/tex]
حالا از دو طرف فرمول بالا لگاریتم میگیریم:
[tex]log(n!) \geq log((n/2)^{(n/2)})[/tex]
حالا طبق این رابطه [tex]log(n^{n})=n*log(n)[/tex] و فرمول بالایی فرمول زیر بدست میاد:
[tex]log(n!) \geq (n/2)log(n/2) \rightarrow {\color{Red} \Omega (nlogn)}[/tex]
ok?
بله mfXpert عزیز اصلاحیه زدند به خط اول پست شون و متوجه شدم ، ممنون از همه دوستان بابت وقتی که گذاشتند.