زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۷:۰۶ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

یه نکته ریز؟!

ارسال:
  

mohabati10 پرسیده:

یه نکته ریز؟!

چرا [tex]Lg(n!)= \Omega (nlgn)[/tex]
??!

۰
ارسال:
  

mfXpert پاسخ داده:

RE: یه نکته ریز؟!

[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. تصحیح شد.

۰
ارسال:
  

mohabati10 پاسخ داده:

RE: یه نکته ریز؟!

ممنون بابت جوابتون. من خط اول رو نفهمیدم! چجوری عبارت وسط از n! کمتر شد؟

یه جواب که برای این مسئله پیدا کردم این هست :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

۰
ارسال:
  

mohabati10 پاسخ داده:

RE: یه نکته ریز؟!

به نظر بنده جواب دوستمون درست نیست دوستان به لینکی که بنده دادم مراجعه کنید تا دچار اشتباه نشوید.

۰
ارسال:
  

Masoud05 پاسخ داده:

RE: یه نکته ریز؟!

یادمه یه جای مانشت این مسئله بررسی شده بود می تونید یه بررسی بفرمایید. جواب آقای mfXpert رو نمی دونم درست هست یا نه چون خیلی روش پیچیده ای بررسی کردن اما اینو بگم که ایشون از بهترین های مانشت در زمینه طراحی الگوریتم هستنSmile

ارسال:
  

golabijat پاسخ داده:

RE: یه نکته ریز؟!

(۲۷ دى ۱۳۹۱ ۱۱:۱۷ ب.ظ)Masoud05 نوشته شده توسط:  یادمه یه جای مانشت این مسئله بررسی شده بود می تونید یه بررسی بفرمایید. جواب آقای mfXpert رو نمی دونم درست هست یا نه چون خیلی روش پیچیده ای بررسی کردن اما اینو بگم که ایشون از بهترین های مانشت در زمینه طراحی الگوریتم هستنSmile

سلام دوست عزیز
جواب 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?TongueTongue
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

mohabati10 پاسخ داده:

یه نکته ریز؟!

بله mfXpert عزیز اصلاحیه زدند به خط اول پست شون و متوجه شدم ، ممنون از همه دوستان بابت وقتی که گذاشتند.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Video دانلود رایگان نکته و تست شبکه های کامپیوتری Farzamm ۱۱ ۱۷,۶۱۰ ۰۷ بهمن ۱۴۰۰ ۰۱:۰۳ ب.ظ
آخرین ارسال: M.rahimi20
  درخواست فیلم نکته تست نظریه دکتر کارگهی juyaye danesh ۰ ۱,۸۰۴ ۲۵ تیر ۱۳۹۹ ۰۱:۰۸ ب.ظ
آخرین ارسال: juyaye danesh
Video دانلود رایگان نکته و تست احتمال و آمار مهندسی Farzamm ۰ ۳,۵۷۴ ۱۸ خرداد ۱۳۹۹ ۰۱:۲۹ ب.ظ
آخرین ارسال: Farzamm
  انتخاب فیلم یا کتاب نکته و تست sima84 ۴ ۳,۶۹۵ ۱۶ اردیبهشت ۱۳۹۹ ۰۸:۳۴ ب.ظ
آخرین ارسال: sima84
  برنامه ریزی و کارهایی که باید انجام بدم fatemesoleimani ۲۰۸ ۶۱,۹۴۹ ۰۲ اسفند ۱۳۹۸ ۱۱:۵۱ ق.ظ
آخرین ارسال: فاطمه سلیمانی
Question یک اشکال ریز، کمک لطفا! marvelous ۶ ۵,۲۲۴ ۳۰ دى ۱۳۹۸ ۰۲:۱۶ ب.ظ
آخرین ارسال: marvelous
Question یک نکته ابهام marvelous ۶ ۴,۷۳۲ ۰۹ دى ۱۳۹۸ ۰۱:۳۰ ب.ظ
آخرین ارسال: marvelous
Question برنامه ریزی به سبک ۳ گام sara417 ۴ ۶,۴۵۸ ۲۰ آذر ۱۳۹۸ ۰۲:۰۴ ق.ظ
آخرین ارسال: marvelous
  [دانلود] جزوه و ویس جلسه نکته تست ساختمان داده والگوریتم استاد یوسفی زمستان ٩٣ software94 ۲۳ ۲۶,۲۴۲ ۰۲ فروردین ۱۳۹۸ ۱۲:۳۲ ق.ظ
آخرین ارسال: honiehs
Sad کمک خواهشا برنامه ریزی ترتیب جزئی Sanazzz ۲ ۲,۷۴۹ ۱۹ بهمن ۱۳۹۷ ۱۰:۲۲ ب.ظ
آخرین ارسال: Sanazzz

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close