22 مرداد 1390, 10:36 ب.ظ
گزینه ۴ صحیح است:
یه راه تستی نوشتن یک آرایه مرتب شده نزولی کوچک می باشد، که این بدترین حالت نیز می باشد مثلاً در ارایه {۱و۲و۳}
اندیس {۳} از {۱و۲} کمتر است اما مقدارش بزرگتر ---> 2 مورد وارونگی
اندیس {۲} از {۱} کمتر اما مقدارش بزرگتر است ---> 1 مورد وارونگی
پس یک سری تولید می شود که در آن مجموع ۱ تا n-1 (در مثال ما از ۱ تا۲ )حساب میشود
نکته: بهترین حالت، یک آرایه صعودی است که در آن هیچ وارونگی نداریم
از آنجاکه احتمال یک وارونگی ۱/۲ می باشد پس باید مقدار بدست امده از مورد بالا (تعداد وارونگی ها) را بر ۲ تقسیم کرد.
توجه داشته باشید که مقدار " بدترین حالت " در واقع تعداد زوج عناصر آرایه می باشد که فرض می کنیم همه دارای وارانگی هستند.
البته راه حل صحیح نوشتن جایگشت همه عناصر آرایه و محاسبه وارونگیها برای تک تک جایگشت عناصر است ،سپس همه مقادیر بدست آمده را جمع کرده و بر !n تقسیم میکنیم تا میانگین کل وارونگی بدست آمده سپس با توجه به فرض مسئله جواب را به ۲ تقسیم میکنیم.