۰
subtitle
ارسال: #۱
  
وارونگی
چرا یافتن تعداد وارونگی ها با اصلاح الگوریتم ادغامی از درجه nlgn میباشد
(توضیحات clrs را خوانده ام و متاسفانه متوجه نشده ام)
(توضیحات clrs را خوانده ام و متاسفانه متوجه نشده ام)
۱
ارسال: #۲
  
RE: وارونگی
همون الگوریتم مرتب سازی ادغامی هستش فقط در قسمتی از الگوریتم که مقایسه و جابجایی انجام میشه یک شمارنده هم قرار میدی، با این شرط که اگر نیاز بود جای دوتا عنصر رو عوض کنی(یعنی اینجا ۱ وارونگی وجود داشته) یکی به شمارنده اضافه کن. (شمارنده رو با این شرط اضافه میکنی)
مرتبه اجرایی مرج سورت هم که همواره nlogn است.
مرتبه اجرایی مرج سورت هم که همواره nlogn است.
ارسال: #۳
  
RE: وارونگی
(۳۰ شهریور ۱۳۹۱ ۰۶:۳۶ ب.ظ)eris229 نوشته شده توسط: همون الگوریتم مرتب سازی ادغامی هستش فقط در قسمتی از الگوریتم که مقایسه و جابجایی انجام میشه یک شمارنده هم قرار میدی، با این شرط که اگر نیاز بود جای دوتا عنصر رو عوض کنی(یعنی اینجا ۱ وارونگی وجود داشته) یکی به شمارنده اضافه کن. (شمارنده رو با این شرط اضافه میکنی)
مرتبه اجرایی مرج سورت هم که همواره nlogn است.
ممنون میشه nlgn را با الگوریتم دیگه ای کمتر کرد
(۳۰ شهریور ۱۳۹۱ ۰۶:۳۷ ب.ظ)m@hboobe نوشته شده توسط: تا زه CLRS خوندم اگر تحلیل اشتباه کردم خواهش میکنم اونایی که تحلیلشون خوبه توضیحاتم یا ویرایش کنن یا تکمیل
خوب اول میگم وارونگی یعنی چی؟! [tex]i < j , A[i]>A[j][/tex]
خب این یعنی یه آرایه که n عضو داره شکسته بشه تا بتونیم عناصر اون رو تک تک با هم مقایسه کنیم و میدونیم که فقط یه ارایه یک عنصری ذاتا مرتب شده است پس توسط merge sort در وهله اول الگوریتم هر بار نصف میکنه تا به تک تک اعداد برسیم
حالا اینجاست که الگوریتم اصلاح میشه و تک تک عناصر با هم چک میشن بجای اینکه دو به دو چک بشن!
تا توضیحات mergرا درست گفتی دوست من اما اگر قرار باشه تک تک عناصر با همگی مقایسه بشند درجه ما n^2 خواهد شد
۰
ارسال: #۴
  
RE: وارونگی
تا زه CLRS خوندم اگر تحلیل اشتباه کردم خواهش میکنم اونایی که تحلیلشون خوبه توضیحاتم یا ویرایش کنن یا تکمیل
خوب اول میگم وارونگی یعنی چی؟! [tex]i < j , A[i]>A[j][/tex]
خب این یعنی یه آرایه که n عضو داره شکسته بشه تا بتونیم عناصر اون رو تک تک با هم مقایسه کنیم و میدونیم که فقط یه ارایه یک عنصری ذاتا مرتب شده است پس توسط merge sort در وهله اول الگوریتم هر بار نصف میکنه تا به تک تک اعداد برسیم
حالا اینجاست که الگوریتم اصلاح میشه و تک تک عناصر با هم چک میشن بجای اینکه دو به دو چک بشن!
خوب اول میگم وارونگی یعنی چی؟! [tex]i < j , A[i]>A[j][/tex]
خب این یعنی یه آرایه که n عضو داره شکسته بشه تا بتونیم عناصر اون رو تک تک با هم مقایسه کنیم و میدونیم که فقط یه ارایه یک عنصری ذاتا مرتب شده است پس توسط merge sort در وهله اول الگوریتم هر بار نصف میکنه تا به تک تک اعداد برسیم
حالا اینجاست که الگوریتم اصلاح میشه و تک تک عناصر با هم چک میشن بجای اینکه دو به دو چک بشن!
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
وارونگی | amir_ghanati | ۲ | ۱,۴۶۶ |
۰۸ دى ۱۳۹۶ ۱۱:۳۲ ق.ظ آخرین ارسال: αɾια |
|
منبع پوشش دهنده وارونگی اولویت در فرایندها | کنکوری | ۲ | ۲,۹۲۸ |
۱۷ دى ۱۳۹۳ ۱۱:۳۶ ب.ظ آخرین ارسال: کنکوری |
|
۴۰۰ نرم افزار.... امید... وارونگی..... | مازیار صفایی | ۸ | ۴,۷۵۲ |
۱۰ خرداد ۱۳۹۱ ۰۲:۳۷ ق.ظ آخرین ارسال: Amir V |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close