(۰۱ اسفند ۱۳۹۵ ۰۶:۲۵ ب.ظ)alireza01 نوشته شده توسط:  

تشکر

در درخت تصمیم تعداد مقایسه ها برای الگوریتم مرتب سازی مقایسه ای در بدترین حالت برابر با ارتفاع درخت است.و ترتیب های ورودی در برگ ها قرار میگیرند.حال در سوال کسری از برگ ها که با cn مقایسه حاصل می شود را پرسیده که معادل تعداد برگ ها در ارتفاع cn و از طرفی حداکثر تعداد برگ در ارتفاع h برابر با [tex]2^h[/tex] پس
[tex]\alpha.n!\le2^{cn}\: \: \: \Longrightarrow\: \alpha\le\frac{2^{cn}}{n!}[/tex]
در نتیجه گزینه ۴ جواب است.
ایا کلید این تست گزینه۴ است ؟ یا من اشتباه کردم؟

(۰۱ اسفند ۱۳۹۵ ۰۹:۰۲ ب.ظ)msour44 نوشته شده توسط:  

(01 اسفند ۱۳۹۵ ۰۶:۲۵ ب.ظ)alireza01 نوشته شده توسط:  

تشکر

در درخت تصمیم تعداد مقایسه ها برای الگوریتم مرتب سازی مقایسه ای در بدترین حالت برابر با ارتفاع درخت است.و ترتیب های ورودی در برگ ها قرار میگیرند.حال در سوال کسری از برگ ها که با cn مقایسه حاصل می شود را پرسیده که معادل تعداد برگ ها در ارتفاع cn و از طرفی حداکثر تعداد برگ در ارتفاع h برابر با [tex]2^h[/tex] پس
[tex]\alpha.n!\le2^{cn}\: \: \: \Longrightarrow\: \alpha\le\frac{2^{cn}}{n!}[/tex]
در نتیجه گزینه ۴ جواب است.
ایا کلید این تست گزینه۴ است ؟ یا من اشتباه کردم؟

بله گزینه ۴ پاسخ صحیح این تست است ، اگر ممکن است بیشتر توضیح دهید .

(۰۱ اسفند ۱۳۹۵ ۰۹:۲۶ ب.ظ)alireza01 نوشته شده توسط:  

(01 اسفند ۱۳۹۵ ۰۹:۰۲ ب.ظ)msour44 نوشته شده توسط:  

(01 اسفند ۱۳۹۵ ۰۶:۲۵ ب.ظ)alireza01 نوشته شده توسط:  

تشکر

در درخت تصمیم تعداد مقایسه ها برای الگوریتم مرتب سازی مقایسه ای در بدترین حالت برابر با ارتفاع درخت است.و ترتیب های ورودی در برگ ها قرار میگیرند.حال در سوال کسری از برگ ها که با cn مقایسه حاصل می شود را پرسیده که معادل تعداد برگ ها در ارتفاع cn و از طرفی حداکثر تعداد برگ در ارتفاع h برابر با [tex]2^h[/tex] پس
[tex]\alpha.n!\le2^{cn}\: \: \: \Longrightarrow\: \alpha\le\frac{2^{cn}}{n!}[/tex]
در نتیجه گزینه ۴ جواب است.
ایا کلید این تست گزینه۴ است ؟ یا من اشتباه کردم؟

بله گزینه ۴ پاسخ صحیح این تست است ، اگر ممکن است بیشتر توضیح دهید .

برای اثبات این قضیه که هر الگوریتم مرتب سازی در بدترین حالت به بیگ اومگای nlogn مقایسه نیاز دارد .به این صورت عمل میکنن با n ورودی !n ترتیب داریم که تمام این ترتیب ها در برگ ها قرار می گیرند و چون در خت تصمیم درختی باینری است پس اگر ارتفاع را h بگیریم حداکثر [tex]2^h[/tex] برگ درخت خواهد داشت پس !nباید کوچکتر مساوی [tex]2^h[/tex] باشد. یعنی
[tex]n!\le2^h\: \: \Longrightarrow\: h\ge\log n!\: \Longrightarrow\: h=\Omega(nlogn)\: [/tex]
به این دلیل ارتفاع را بدست می اورند چون برابر با حداقل تعداد مقایسه در بدترین حالت است در این سوال تعداد مقایسه رو cn 'می خواد یعنی همون ارتفاع cn که در این ارتفاع باید به تریبی مرتب شده برسیم یعنی برگی که حاوی اون ترتیب است از طرفی در ارتفاع cn حداکثر[tex]2^{cn}[/tex] برگ وجود دارد
که تعداد برگ های مورد نظر سوال(درصدی از کل برگها [tex]\alpha.n![/tex]) از این [tex]2^{cn}[/tex] باید کوچکتر باشه.
البته بحث برگ های قابل دسترس هم وجود داره که دیگه برای ساده سازی از ان چشم پوشی شد.
اگه توضیحاتم ناقص یا خوب نیست عذرخواهی میکنم.