نقل قول:
نوشته اصلي بوسيله narssic
سوال 14 دقیقا از کتاب دکتر قدسی اومده، صفحه 22 سوال 25.2
جواب در صفحه 196:
اگر در هر مرحله، الگوریتم مرتب سازی سریع تصادفی بزرگترین (یا کوچکترین) عنصر را بعنوان محور انتخاب کند، در آن صورت این الگوریتم مانند مرتب سازی سریع قطعی بر روی آرایه ای مرتب است که در زمان O(n^2) این کار را انجام می دهد احتمال این که چنین حالتی پیش بیاید برابر است با 1/(n^2) - یک روی n بتوان 2-
|
مگه جواب 1 به روی n فاکتوریل نشد؟
پس چرا گفتین 1 رو n به توان دو
من یه چیزی به ذهنم رسید. مگه در هرمرحله احتمال اینکه بزرگترین یا کوچکترین انتخاب شوند 2 روی n نیست و اگر در تمام مراحل به این صورت باشه خوب در گامهای بعدی میشه 2 روی n-1,
2 روی n-2 الی آخر . در هر مرحله از n یکی کم شده چون در هر گام جای اون عنصر بزرگترین یا کوچکترین مشخص میشه پس احتمال کل میشه
(2^n/n!)
دو به توان n روی n فاکتوریل. حالا چرا میشه گزینه دو. سه و چهار هم میشه تازه به جواب نزدیکتره