سلام بچه ها میشه حل اینو توضیح بدید!!!
برای پیدا کردن میانه(median) بین n عدد در حالتی که n=5 ، n=3 به ترتیب حداقل چند مقایسه نیاز داریم؟(از چپ به راست)
۱-[tex]3,6[/tex]
۲-[tex]3,10[/tex]
۳-[tex]2,6[/tex]
۴-[tex]2,10[/tex]
تو بخش تقسیم غلبه ی پوران یه فرمول خوشگل داره که به راحتی این تست ها حل می شن ولی حفظ کردنش یه کوچولو سخته:
حد پایین برای یافتن i امین کوچکترین کلید در بین n عنصر برای i>1 عبارتست از :
[tex]n (i-1)\lceil\lg(\frac{n}{i-1})\rceil-i\: \: \in\theta(n)[/tex]
حالا فقط کافیه که بدونیم میانه ی ۳ عنصر یعنی دومین کوچکترین عنصر که تعداد مقایسه هاش می شه :
[tex]3 (2-1)\lceil\lg(\frac{3}{2-1})\rceil-2\: \: =3 1(2)-2=3[/tex]
و میانه ی ۵ عنصر می شه سومین کوچکترین عنصر که تعداد مقایسه هاش می شه:
[tex]5 (3-1)\lceil\lg(\frac{5}{3-1})\rceil-3\: \: =5 2(2)-3=6[/tex]
اوه اوه چه روشی!!!!واقعا خوشم اومد مرسسسسسییییییییی
البته فرمول رو میشه کوتاه کرد.
به نظرم اینم جواب میده:
[tex]n \lceil\log n\rceil-2[/tex]