سلام.
در سوال ۹۷ آزمون ۵۰ درصد دوم پارسه گفته شده است ، "برای مرتب سازی ۷ عنصر با روش مبتنی بر مقایسه در بدترین حالت ۱۳ مقایسه لازم است" ولی به نظر من خیلی بیشتر از این ها می شود. به عنوان مثال فرض کنید Quick Sort در حالت بدترین باشد (یعنی آرایه مرتب باشد) در این حالت تعداد مقایسات از مرتبه n به توان ۲ خواهد بود. لطفا بفرمایید این جمله صحیح است یا نه و اگر صحیح است چرا؟
![[تصویر: 234846_Q97.jpg]](https://img.manesht.ir/234846_Q97.jpg)
این جور بحثا فارغ از الگوریتم مرتب سازی هستش و شما نمیتونی با یه الگوریتم خاص نتیجه گیری کنی، نکته اینه که وقتی شما درخت مقایسه رو میسازی بلند ترین مسیر، میشه بدترین حالت اجرا که ممکنه توی مرتب سازی سریع اتفاق بیافته یا اصلا یه الگوریتمی که هیشکی تا حالا کشف نکرده.
(۱۴ دى ۱۳۹۲ ۰۶:۳۹ ب.ظ)Riemann نوشته شده توسط: این جور بحثا فارغ از الگوریتم مرتب سازی هستش و شما نمیتونی با یه الگوریتم خاص نتیجه گیری کنی، نکته اینه که وقتی شما درخت مقایسه رو میسازی بلند ترین مسیر، میشه بدترین حالت اجرا که ممکنه توی مرتب سازی سریع اتفاق بیافته یا اصلا یه الگوریتمی که هیشکی تا حالا کشف نکرده.
ممنونم.
چطور باید فهمید که منظور سوال درخت مقایسه است و نباید یک الگوریتم مرتب سازی خاص را که می تواند شرایط خیلی بدی داشته باشد در نظر داشت ؟ آیا از اینکه در گزاره قبل در این مورد صحبت کرده باید چنین برداشتی داشت یا اینکه در گزاره دوم مطلبی نهفته است که گویای این موضوع است ؟
اگر چنین است آن مطلب را لطفا بفرمایید.
فکر کنم چون گفته مبتنی بر مقایسه میشه منظورشو درخت تصمیم در نظر گرفت
(۱۴ دى ۱۳۹۲ ۰۸:۴۷ ب.ظ)masoud67 نوشته شده توسط: فکر کنم چون گفته مبتنی بر مقایسه میشه منظورشو درخت تصمیم در نظر گرفت
سپاس فراوان.