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

حد پایین در الگوریتم های مرتب سازی مبتنی بر مقایسه

پاسخ جدید به سوال اصلی موضوع
۲
subtitle
ارسال: #۱
  

e.shrm پرسیده:

حد پایین در الگوریتم های مرتب سازی مبتنی بر مقایسه

سلام
یک سوالی برام پیش اومد.
مگه بر اساس درخت تصمیم به این نتیجه نرسیدیم که حد پایین برای مرتب سازی ها در الگوریتم های مبتنی بر مقایسه nlogn هست؟
ولی ما در مرتب سازی درجی که خب مبتنی بر مقایسه هست ، حد پایین n داریم ، بعد این دو تا با هم تناقض نداره؟
نقل قول این ارسال در یک پاسخ

۱
ارسال: #۲
  

mhm-pc پاسخ داده:

RE: حد پایین در الگوریتم های مرتب سازی مبتنی بر مقایسه

باید بدترین حالت الگوریتم های مرتب سازی را با این حد پایین ( nlogn ) مقایسه کنید.
نقل قول این ارسال در یک پاسخ

ارسال: #۳
  

e.shrm پاسخ داده:

RE: حد پایین در الگوریتم های مرتب سازی مبتنی بر مقایسه

(۰۳ آذر ۱۳۹۲ ۱۱:۴۶ ق.ظ)mhm-pc نوشته شده توسط:  باید بدترین حالت الگوریتم های مرتب سازی را با این حد پایین ( nlogn ) مقایسه کنید.

من متوجه اشتباهم شدم. نه بدترین حالت نیست ، باید حالت متوسط ها رو مقایسه کنیم. clrs اینجوری گفته.
ممنون
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۱
ارسال: #۴
  

mhm-pc پاسخ داده:

RE: حد پایین در الگوریتم های مرتب سازی مبتنی بر مقایسه

نه
حالت میانگین اصلا اینجا معنی نمیده. قضیه یی که توی کتاب گفته اینه: هر الگوریتم مرتب سازی در بدترین حالت به Ω(nlgn) مقایسه احتیاج دارد.
معنی خودمونیش اینه که مرتبه زمانی هر الگوریتم مرتب سازی در بدترین حالت بزرگتر و مساوی n lg n است.
نقل قول این ارسال در یک پاسخ

ارسال: #۵
  

e.shrm پاسخ داده:

RE: حد پایین در الگوریتم های مرتب سازی مبتنی بر مقایسه

(۰۳ آذر ۱۳۹۲ ۱۲:۵۴ ب.ظ)mhm-pc نوشته شده توسط:  نه
حالت میانگین اصلا اینجا معنی نمیده. قضیه یی که توی کتاب گفته اینه: هر الگوریتم مرتب سازی در بدترین حالت به Ω(nlgn) مقایسه احتیاج دارد.
معنی خودمونیش اینه که مرتبه زمانی هر الگوریتم مرتب سازی در بدترین حالت بزرگتر و مساوی n lg n است.

آهان. فکر کنم فهمیدم. ممنون
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۶
  

zahraaahmadi29 پاسخ داده:

RE: حد پایین در الگوریتم های مرتب سازی مبتنی بر مقایسه

سلام دوستان، در تست کنور سراسری سال ۹۱ حداقل مقایسه ها رو در بدترین حالت از
n log n!
چررااااا؟
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

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


موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  چه جوری با سطح زبان انگلیسی تقریبا پایین رفرنس بخونیم؟ saharitst ۰ ۱,۷۴۲ ۲۱ آبان ۱۴۰۰ ۰۴:۱۱ ب.ظ
آخرین ارسال: saharitst
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۷,۳۴۶ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  مرتب سازی سریع تصادفی چیست؟ Xzrix ۰ ۱,۷۵۳ ۱۴ آذر ۱۳۹۹ ۰۷:۲۲ ب.ظ
آخرین ارسال: Xzrix
  شبیه سازی مقاله Q-Learning kadoos ۱۶ ۱۹,۱۱۸ ۲۵ آبان ۱۳۹۹ ۰۹:۱۹ ب.ظ
آخرین ارسال: nasim.nasim۱
Sad ذخیره ماتریس پایین مثلثی / بالا مثلثی به شیوه سطری یا ستونی shayesteNEY ۵ ۱۱,۵۸۴ ۲۲ مهر ۱۳۹۹ ۱۱:۲۸ ب.ظ
آخرین ارسال: Negiiin
  کتاب شبیه سازی آمنت omnet++ berkeley ۱ ۴,۴۷۶ ۰۴ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ق.ظ
آخرین ارسال: محمد رستمی
  مقایسه دانشگاه ها imali ۲ ۳,۳۹۵ ۰۵ مهر ۱۳۹۸ ۱۲:۲۵ ق.ظ
آخرین ارسال: imali
  افزایش واگرایی الگوریتم های مبتنی بر جمعیت moslem73421 ۲ ۳,۶۰۳ ۰۵ شهریور ۱۳۹۸ ۱۰:۵۳ ب.ظ
آخرین ارسال: cpt.mazi
  برای استخدام به اخرین مدرک نگاه میکنن یا میشه مدرک پایین تر ارائه داد؟ R.g- ۴ ۵,۲۵۱ ۲۰ مرداد ۱۳۹۸ ۰۹:۲۵ ب.ظ
آخرین ارسال: marvelous
  دانلود آموزش تصویری کلاس درس تحلیل و طراحی الگوریتم های پیشرفته دانشگاه فردوسی jazana ۱۳ ۱۵,۱۸۵ ۱۰ خرداد ۱۳۹۸ ۰۵:۴۲ ب.ظ
آخرین ارسال: Valipourh20

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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