انجمنصفحه اولجستجوی انجمن

[Masoud05]

---

گزینه ۴ صحیح است:
یه راه تستی نوشتن یک آرایه مرتب شده نزولی کوچک می باشد‌، که این بدترین حالت نیز می باشد مثلاً در ارایه {۱و۲و۳}
اندیس {۳} از {۱و۲} کمتر است اما مقدارش بزرگتر ---> 2 مورد وارونگی
اندیس {۲} از {۱} کمتر اما مقدارش بزرگتر است ---> 1 مورد وارونگی
پس یک سری تولید می شود که در آن مجموع ۱ تا n-1 (در مثال ما از ۱ تا۲ )حساب میشود

نکته‌: بهترین حالت‌، یک آرایه صعودی است که در آن هیچ وارونگی نداریم
از آنجاکه احتمال یک وارونگی ۱/۲ می باشد پس باید مقدار بدست امده از مورد بالا (تعداد وارونگی ها) را بر ۲ تقسیم کرد.

توجه داشته باشید که مقدار " بدترین حالت " در واقع تعداد زوج عناصر آرایه می باشد که فرض می کنیم همه دارای وارانگی هستند.

---

البته راه حل صحیح نوشتن جایگشت همه عناصر آرایه و محاسبه وارونگی‌ها برای تک تک جایگشت عناصر است ،سپس همه مقادیر بدست آمده را جمع کرده و بر !n تقسیم میکنیم تا میانگین کل وارونگی بدست آمده سپس با توجه به فرض مسئله جواب را به ۲ تقسیم میکنیم.

[پشتکار]

اگه امکانش هست مبتدی‌تر توضیح بدید

[Masoud05]

(۲۳ مرداد ۱۳۹۰ ۱۲:۴۰ ب.ظ)پشتکار نوشته شده توسط:  اگه امکانش هست مبتدی‌تر توضیح بدید

تعداد وارونگیها رو بدست بیار و نتیجه رو تقسیم بر ۲/ ارسال قبلیم رو ویرایش کردم و یه مورد که شاید شما رو به شک مینداخت حذف کردم .