اول شکل ۱ ضمیمه را دانلود کنید همین طور در شکل نشان داده شده در اجرای عملیات مرتب سازی ادغامی روابط نشان داده شده بین طول هر صف و ارتفاع درخت از ریشه تا مکان آن صف ارتباطی وجود دارد. در شکل n=8 می باشد . در هر مرحله اگر طول هر صف v باشد و ارتفاع از ریشه درخت تا مکان صف های ان مرحله w باشد داریم
(v) ضربدر ( تعداد صف به طول v ) = n
( تعداد صف به طول v ) = [tex]2^{w}[/tex]
از دو رابطه بالا نتیجه می شود
[tex]2^{w}\times v=n[/tex]
حالا که این مقدمه گفته شد بریم سراغ صورت سوال
فرض کنید b توانی از ۲ باشد شکل ۲ ضمیمه شده را دانلود کنید همان طور که در صورت سوال کفته و در شکل نشان داده شده هزینه ادغام هر دو صف از زمانی که طول هر صف b/2 یا کمتر باشد برابر O(1 می باشد زیرا می دانیم حداکثر فاصله (از نظر اختلاف اندیس) بین دو صفی که باید با هم ترکیب شوند کمتر از b می باشد پس هزینه هر مرجله که دارای صف هایی با طول b/2 یا کمتر باشد برابر O(1 می باشد.
ولی اگر طول صف b یا بیشتر باشد هزینه هر مرحله ادغام برابر o(n می باشد برای اثبات این موضوع فرض کنید در مرحله ای هستید که طول تمام صف ها k می باشد و تعداد کل این صف ها z می باشد حال بر طبق الگوریتم مرتب سازی ادغامی هر دو صف مرتب با طول k برای تولید صف مرتب با طول ۲k در هم ادغام می شوند.
می دانیم هزینه ترکیب دو صف مرتب (تعداد مقایسه ها) به طول m وn حداکثر برابر m+n-1 می باشد
پس هزینه تولید هر صف با طول ۲k از دو صف با طول k برابر ۲k-1 می باشد و چون در کل zتا صف با طول k داشتیم پس از اجرای الگوریتم ترکیب کردن صف ها، به تعداد z/2 صف با طول ۲k داریم پس در کل هزینه این مرحله (تعداد کل مقایسه های صورت گرفته شده) برابر است با
( ۲k-1)(z/2)
همانطور که در بالا درباره شکل ۱ و اولین معادله آن گفته شد رابطه ضرب kz=n برقرار است. پس در کل هزینه هر مرجله برابر است با
[tex]O((2k-1)(\frac{z}{2}))= O(kz)=O(n)[/tex]
خوب جالا که هزینه هر مرجله را می دانیم برای حساب هزینه کل باید تعداد مرحله ها را بدانیم تا با ضرب کردن تعداد مرحله در هزینه هر مرحله هزینه کل را به دست آوریم. و همان طور در شکل ۲ نبز مشهود است تعداد مرحله هایی که هزینه ان مرحله ها o(n) می باشد برابر باارتفاع درخت ار ریشه تا مکان صف ها با طول b می باشد. که برای محاسبه این طول از سومین فرمولی که درباره شکل ۱ گفته شد استفاده می کنیم. تعداد مرحله ها را با r نشان می دهیم.
[tex]2^{r}\times b=n =>r =log(\frac{n}{b})[/tex]
پس هزینه کل برابر است با
[tex]O(log(\frac{n}{b})O(n))=O(nlog(\frac{n}{b})[/tex]

در بالا فرض کردیم b توانی از ۲ باشد حتی اگر b توانی از ۲ نیاشد با توجه به توضیحات گفته شده گ۱ درست هست

دوستان کمکم کنید من این سوالو متوجه نمیشم .

بسیار ممنونم واقعا شرمنده ام میدونم برای جواب دادن به این سوال خیلی از وقتتون گرفته شده منو ببخشید

خیلی خیلی خیلی توضیحتون کامل بود من فقط یه جایی رو متوجه نشدم همون اوایل که گفتید((همان طور که در صورت سوال کفته و در شکل نشان داده شده هزینه ادغام هر دو صف از زمانی که طول هر صف b/2 یا کمتر باشد برابر O(1 می باشد زیرا می دانیم حداکثر فاصله (از نظر اختلاف اندیس) بین دو صفی که باید با هم ترکیب شوند کمتر از b می باشد پس هزینه هر مرجله که دارای صف هایی با طول b/2 یا کمتر باشد برابر O(1 می باشد.))
سوال من اینه که سوال گفته که وقتی j-i<<b باشد برابر صفر در غیر اینصورت هزینه یک میشود. یعنی زمانی که میخواییم دو عنصر رو با هم ادغام کنیم اگر اختلافشون از b کمتر یا مساوی بشه صفر میشه ولی اگرj-i>b هزینه یک میشود خوب شما دارید میگید b/2 یا کمتر باشد برابر O(1 مشه من این جملتونو متوجه نمیشم چطور استدلال کردید؟؟

اگر بگید ممنون میشم.

(۲۰ آذر ۱۳۹۲ ۰۸:۱۸ ب.ظ)tarane1992 نوشته شده توسط:  بسیار ممنونم واقعا شرمنده ام میدونم برای جواب دادن به این سوال خیلی از وقتتون گرفته شده منو ببخشید

خیلی خیلی خیلی توضیحتون کامل بود من فقط یه جایی رو متوجه نشدم همون اوایل که گفتید((همان طور که در صورت سوال کفته و در شکل نشان داده شده هزینه ادغام هر دو صف از زمانی که طول هر صف b/2 یا کمتر باشد برابر O(1 می باشد زیرا می دانیم حداکثر فاصله (از نظر اختلاف اندیس) بین دو صفی که باید با هم ترکیب شوند کمتر از b می باشد پس هزینه هر مرجله که دارای صف هایی با طول b/2 یا کمتر باشد برابر O(1 می باشد.))
سوال من اینه که سوال گفته که وقتی j-i<<b باشد برابر صفر در غیر اینصورت هزینه یک میشود. یعنی زمانی که میخواییم دو عنصر رو با هم ادغام کنیم اگر اختلافشون از b کمتر یا مساوی بشه صفر میشه ولی اگرj-i>b هزینه یک میشود خوب شما دارید میگید b/2 یا کمتر باشد برابر O(1 مشه من این جملتونو متوجه نمیشم چطور استدلال کردید؟؟

اگر بگید ممنون میشم.

این را قبول داریم که هرینه ترکیب دو صف که طول هر صف b/2 یا کمتر هست صفر می باشد پس یعنی هزینه برابر یک مقدار ثابت (در اینجا صفر) می باشد. از نظر مجانبی اگر k یک عدد ثابت باشد داریم
O(k)=O(1