(۰۹ آبان ۱۳۹۵ ۱۲:۴۳ ب.ظ)mostafaheydar1370 نوشته شده توسط:  حل سوال زیربه چه صورت است ؟

در بدترین حالت، یعنی وقتی که همه‌ی n تا وزنه وزن مختلفی داشته باشند، تعداد کل حالات [tex]n![/tex] هست و جوابِ درست، یکی از این [tex]n![/tex] حالت هست.
هر مقایسه‌ای که انجام میدیم، نصف این حالات حذف میشه. مثلاً وقتی میدونیم وزنه‌ی x از y سنگین‌تر هست، تمامی حالاتی که داخلشون x قبل از y اومده حذف میشه، که میشه نصف حالات.
پس جواب دقیقاً عبارت است از [tex]T(n!)=T(\frac{n!}{2})+1= \theta (\lceil \log(n!) \rceil )[/tex]. روشش هم اینطوری هست که هر بار به پترن‌های موجود (جایگشت‌های موجود) نگاه کنیم و دو تا متغیر رو با هم مقایسه کنیم، تا ترتیب اصلی‌شون به دست بیاد و نصف حالات حذف بشه.
البته [tex]\log(n!)[/tex] هم معادل با همون [tex]nlog(n)[/tex] هست ولی اینجا جواب دقیق خواسته.

با حدف گزینه هم میشه جواب داد. برای دو وزنه، فقط یک مقایسه نیاز هست، پس گزینه‌ی ۲ و ۳ نمیشه. برای ۳ وزنه هم ۳ مقایسه نیاز هست، پس گزینه‌ِ ۴ هم نمیشه.