سلام
من می دونم که در مرتب سازی حبابی پیچیدگی زمانی به تعداد جابجایی ها وابسته است و در حالت کلی
[tex]\frac{n(n-1)}{2}[/tex]
جابجایی داریم که به طور متوسط انتظار داریم نصفشون انجام بشه. پس تعداد مورد انتظار جابجایی با فرض توزیه ورودی یکنواخت میشه اینقدر:
[tex]\frac{n(n-1)}{۴}[/tex]
اما راه حل دقیقش رو از طریق امید ریاضی می خوام. کسی میتونه کمک کنه؟
چی شد؟ کسی جوابی نداره برای این سوال؟ پیچیدگی زمانی در حالت متوسط برای مرتب سازی درجی رو هم می خام. اگه کسی میتونه لطفا کمک کنه.
من خودم یه چیزایی به ذهنم میرسه ولی نمی تونم کاملش کنم
اگر آرایه مرتب باشه با یک پیمایش از برنامه خارج میشیم پس احتمالش و تعداد اجراش به صورت زیر میشه
[tex]\frac{1}{n!}\longrightarrow(n-1)[/tex]
اگر بعد از یک بار پیمایش به یک آرایه مرتب برسیم احتمالش و تعداد اجراش فکر می کنم اینطوری بشه
[tex]\frac{(n-1)+(n-1)(n-2)+...+(n-1)
(n-2)...1_{ }}{n!}\longrightarrow(n-1)+(n-2)[/tex]
نهایتا همه اینا باید دوتا دوتا در هم ضرب و نتایج جمع بشن. میدونمم احتمالا جوابش باید بشه
[tex]\frac{n(n-1)}{4}[/tex]
کسی نمیتونه کمک کنه به یک راه حا صریح و شفاف برسیم؟