زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۱۱:۱۵ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

مرتب سازی

ارسال:
  

alireza01 پرسیده:

مرتب سازی



تشکر
نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

msour44 پاسخ داده:

RE: مرتب سازی

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

تشکر

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

ارسال:
  

alireza01 پاسخ داده:

RE: مرتب سازی

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

تشکر

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

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

ارسال:
  

msour44 پاسخ داده:

RE: مرتب سازی

(۰۱ اسفند ۱۳۹۵ ۰۹:۲۶ ب.ظ)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] باید کوچکتر باشه.
البته بحث برگ های قابل دسترس هم وجود داره که دیگه برای ساده سازی از ان چشم پوشی شد.
اگه توضیحاتم ناقص یا خوب نیست عذرخواهی میکنم.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۲۸۶ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  مرتب سازی سریع تصادفی چیست؟ Xzrix ۰ ۱,۳۶۸ ۱۴ آذر ۱۳۹۹ ۰۷:۲۲ ب.ظ
آخرین ارسال: Xzrix
  شبیه سازی مقاله Q-Learning kadoos ۱۶ ۱۵,۱۴۵ ۲۵ آبان ۱۳۹۹ ۰۹:۱۹ ب.ظ
آخرین ارسال: nasim.nasim۱
  کتاب شبیه سازی آمنت omnet++ berkeley ۱ ۳,۸۳۷ ۰۴ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ق.ظ
آخرین ارسال: محمد رستمی
  سئو چیست؟ - سئو - بهینه سازی سایت msnmsn ۲ ۲۴ ۲۳ آبان ۱۳۹۸ ۰۱:۱۳ ب.ظ
آخرین ارسال: xiaomi
  مجموعه آموزش تصویری ابزار شبیه سازی و بررسی پروتکل امنیتی اسکایتر net work ۰ ۲,۳۱۷ ۲۲ فروردین ۱۳۹۸ ۰۳:۲۵ ب.ظ
آخرین ارسال: net work
  برگ برگ سازی Sanazzz ۱ ۱,۹۰۲ ۱۳ فروردین ۱۳۹۸ ۰۸:۱۸ ب.ظ
آخرین ارسال: Sanazzz
  راهنمایی برای انتخاب موضوع قابل پیاده سازی در زمینه بیگ دیتا برای پایان نامه one hacker alone ۱ ۲,۹۸۸ ۱۸ بهمن ۱۳۹۷ ۰۶:۳۶ ب.ظ
آخرین ارسال: Happiness.72
  ابزار شبیه سازی پروتکل های امنیت شبکه - ابزار اسکایتر mavin1200 ۰ ۲,۱۲۹ ۰۱ آذر ۱۳۹۷ ۰۱:۵۰ ق.ظ
آخرین ارسال: mavin1200
  بهینه سازی چند هدفه فازی استوارژنتیک alighasemi ۰ ۱,۹۰۰ ۲۴ آبان ۱۳۹۷ ۰۴:۵۵ ب.ظ
آخرین ارسال: alighasemi

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close