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