چرا یافتن تعداد وارونگی ها با اصلاح الگوریتم ادغامی از درجه nlgn میباشد
(توضیحات clrs را خوانده ام و متاسفانه متوجه نشده ام)
همون الگوریتم مرتب سازی ادغامی هستش فقط در قسمتی از الگوریتم که مقایسه و جابجایی انجام میشه یک شمارنده هم قرار میدی، با این شرط که اگر نیاز بود جای دوتا عنصر رو عوض کنی(یعنی اینجا ۱ وارونگی وجود داشته) یکی به شمارنده اضافه کن. (شمارنده رو با این شرط اضافه میکنی)
مرتبه اجرایی مرج سورت هم که همواره nlogn است.
تا زه CLRS خوندم اگر تحلیل اشتباه کردم خواهش میکنم اونایی که تحلیلشون خوبه توضیحاتم یا ویرایش کنن یا تکمیل
خوب اول میگم وارونگی یعنی چی؟! [tex]i < j , A[i]>A[j][/tex]
خب این یعنی یه آرایه که n عضو داره شکسته بشه تا بتونیم عناصر اون رو تک تک با هم مقایسه کنیم و میدونیم که فقط یه ارایه یک عنصری ذاتا مرتب شده است پس توسط merge sort در وهله اول الگوریتم هر بار نصف میکنه تا به تک تک اعداد برسیم
حالا اینجاست که الگوریتم اصلاح میشه و تک تک عناصر با هم چک میشن بجای اینکه دو به دو چک بشن!
(۳۰ شهریور ۱۳۹۱ ۰۶:۳۶ ب.ظ)eris229 نوشته شده توسط: همون الگوریتم مرتب سازی ادغامی هستش فقط در قسمتی از الگوریتم که مقایسه و جابجایی انجام میشه یک شمارنده هم قرار میدی، با این شرط که اگر نیاز بود جای دوتا عنصر رو عوض کنی(یعنی اینجا ۱ وارونگی وجود داشته) یکی به شمارنده اضافه کن. (شمارنده رو با این شرط اضافه میکنی)
مرتبه اجرایی مرج سورت هم که همواره nlogn است.
ممنون میشه nlgn را با الگوریتم دیگه ای کمتر کرد
(۳۰ شهریور ۱۳۹۱ ۰۶:۳۷ ب.ظ)m@hboobe نوشته شده توسط: تا زه CLRS خوندم اگر تحلیل اشتباه کردم خواهش میکنم اونایی که تحلیلشون خوبه توضیحاتم یا ویرایش کنن یا تکمیل
خوب اول میگم وارونگی یعنی چی؟! [tex]i < j , A[i]>A[j][/tex]
خب این یعنی یه آرایه که n عضو داره شکسته بشه تا بتونیم عناصر اون رو تک تک با هم مقایسه کنیم و میدونیم که فقط یه ارایه یک عنصری ذاتا مرتب شده است پس توسط merge sort در وهله اول الگوریتم هر بار نصف میکنه تا به تک تک اعداد برسیم
حالا اینجاست که الگوریتم اصلاح میشه و تک تک عناصر با هم چک میشن بجای اینکه دو به دو چک بشن!
تا توضیحات mergرا درست گفتی دوست من اما اگر قرار باشه تک تک عناصر با همگی مقایسه بشند درجه ما n^2 خواهد شد