(۲۸ آذر ۱۳۹۱ ۰۹:۳۴ ق.ظ)jafarir نوشته شده توسط:  سلام خدمت دوستان محترم
- در الگوریتم mergsort اگر بجای آنکه هر لیست به ۲ قسمت مساوی تقسیم شود ، به ۴ قسمت مساوی تقسیم گردد و در مرحله ی ترکیب این ۴ لیست در یکدیگر ادغام شوند ، تعداد صدا زدن در لیست زیر؟

۳۱۰,۲۸۵,۱۷۹,۶۵۲,۳۵۱,۴۲۳,۸۶۱,۲۵۴,۴۵۰,۵۲۰

سلام
خوب چون شما فقط دنبال تعداد صدا زدن ها هستی رابطه بازگشتی شما میشود :
[tex]T(n)=4T(\frac{n}{4}) 1[/tex]
و در نظر بگیر که برای آرایه با یک عنصر فقط یک فراخوانی انجام میپذیرد.
حال تعداد عناصر لیست خودت رو بشمار که می شود ۱۰ عدد و بزار داخل رابطه بازگشتی و حسابش کن ...

به نظرم یک راه دیگه بدون استفاده از فرمول اینه که به ازای هر باز خرد کردن تا رسیدن به تک عناصر یکبار فراخوانی و به ازای ادغام عناصر تکی تا رسیدن به ادغام کل عناصر در یک ارایه هر بار ادغام یکبار.

(۲۸ آذر ۱۳۹۱ ۱۲:۳۹ ب.ظ)m_sardaari نوشته شده توسط:  به نظرم یک راه دیگه بدون استفاده از فرمول اینه که به ازای هر باز خرد کردن تا رسیدن به تک عناصر یکبار فراخوانی و به ازای ادغام عناصر تکی تا رسیدن به ادغام کل عناصر در یک ارایه هر بار ادغام یکبار.

شرمنده ، منظورتون اینه که ۱ فراخوانی به ازای کل عناصر آرایه ولی قسمت دومش رو متوجه نمیشم ، یعنی چی که هر بار ادغام یکبار؟؟؟
ممنون میشم توضیح بیشتر بدین

به نظر من هم جواب M_sardaari درست هست چون اینجوری جواب دقیق بدست میاد نه با فرمول ،اما واسه تقسیم به ۴ هم من اشکال دارم دقیقا نمیدونم جواب چی میشه

(۲۹ آذر ۱۳۹۱ ۰۹:۴۹ ق.ظ)jafarir نوشته شده توسط:  

(28 آذر ۱۳۹۱ ۱۲:۳۹ ب.ظ)m_sardaari نوشته شده توسط:  به نظرم یک راه دیگه بدون استفاده از فرمول اینه که به ازای هر باز خرد کردن تا رسیدن به تک عناصر یکبار فراخوانی و به ازای ادغام عناصر تکی تا رسیدن به ادغام کل عناصر در یک ارایه هر بار ادغام یکبار.

شرمنده ، منظورتون اینه که ۱ فراخوانی به ازای کل عناصر آرایه ولی قسمت دومش رو متوجه نمیشم ، یعنی چی که هر بار ادغام یکبار؟؟؟
ممنون میشم توضیح بیشتر بدین

هر بار که ارایه رو به ۴ قسمت تقسیم میکنیم یکبار فراخوانی.
هر بار که عناصر تک عضوی رو با هم ادغام میکنیم هم یکبار فراخوانی
البته این فراخوانی ها مربوط به رویه merge هستن و نه رویه merge sort .
و نکته ی دیگه ای که داره اگر برای مرتب سازی ادغامی ارایه رو به هر تعداد دسته ( ۲تایی.۵تایی .۱۰ تایی ...) تقسیم کنیم مرتبه این الگوریتم همون nlogn میمونه و تغییر نمیکنه که با تابع زمانیش قابل اثباته.یعنی اگر در تابع زمانی که دوستمون گذاشت به جا ۴ هر عدد دیگه ای بزاریم بازم مرتبه nlogn میشه.