سلام خدمت دوستان محترم
- در الگوریتم mergsort اگر بجای آنکه هر لیست به ۲ قسمت مساوی تقسیم شود ، به ۴ قسمت مساوی تقسیم گردد و در مرحله ی ترکیب این ۴ لیست در یکدیگر ادغام شوند ، تعداد صدا زدن در لیست زیر؟
۳۱۰,۲۸۵,۱۷۹,۶۵۲,۳۵۱,۴۲۳,۸۶۱,۲۵۴,۴۵۰,۵۲۰
(۲۸ آذر ۱۳۹۱ ۰۹:۳۴ ق.ظ)jafarir نوشته شده توسط: سلام خدمت دوستان محترم
- در الگوریتم mergsort اگر بجای آنکه هر لیست به ۲ قسمت مساوی تقسیم شود ، به ۴ قسمت مساوی تقسیم گردد و در مرحله ی ترکیب این ۴ لیست در یکدیگر ادغام شوند ، تعداد صدا زدن در لیست زیر؟
۳۱۰,۲۸۵,۱۷۹,۶۵۲,۳۵۱,۴۲۳,۸۶۱,۲۵۴,۴۵۰,۵۲۰
سلام
خوب چون شما فقط دنبال تعداد صدا زدن ها هستی رابطه بازگشتی شما میشود :
[tex]T(n)=4T(\frac{n}{4}) 1[/tex]
و در نظر بگیر که برای آرایه با یک عنصر فقط یک فراخوانی انجام میپذیرد.
حال تعداد عناصر لیست خودت رو بشمار که می شود ۱۰ عدد و بزار داخل رابطه بازگشتی و حسابش کن ...
به نظرم یک راه دیگه بدون استفاده از فرمول اینه که به ازای هر باز خرد کردن تا رسیدن به تک عناصر یکبار فراخوانی و به ازای ادغام عناصر تکی تا رسیدن به ادغام کل عناصر در یک ارایه هر بار ادغام یکبار.
(۲۸ آذر ۱۳۹۱ ۱۲:۳۹ ب.ظ)m_sardaari نوشته شده توسط: به نظرم یک راه دیگه بدون استفاده از فرمول اینه که به ازای هر باز خرد کردن تا رسیدن به تک عناصر یکبار فراخوانی و به ازای ادغام عناصر تکی تا رسیدن به ادغام کل عناصر در یک ارایه هر بار ادغام یکبار.
شرمنده ، منظورتون اینه که ۱ فراخوانی به ازای کل عناصر آرایه ولی قسمت دومش رو متوجه نمیشم ، یعنی چی که هر بار ادغام یکبار؟؟؟
ممنون میشم توضیح بیشتر بدین
به نظر من هم جواب M_sardaari درست هست چون اینجوری جواب دقیق بدست میاد نه با فرمول ،اما واسه تقسیم به ۴ هم من اشکال دارم دقیقا نمیدونم جواب چی میشه
(۲۹ آذر ۱۳۹۱ ۰۹:۴۹ ق.ظ)jafarir نوشته شده توسط:هر بار که ارایه رو به ۴ قسمت تقسیم میکنیم یکبار فراخوانی.(28 آذر ۱۳۹۱ ۱۲:۳۹ ب.ظ)m_sardaari نوشته شده توسط: به نظرم یک راه دیگه بدون استفاده از فرمول اینه که به ازای هر باز خرد کردن تا رسیدن به تک عناصر یکبار فراخوانی و به ازای ادغام عناصر تکی تا رسیدن به ادغام کل عناصر در یک ارایه هر بار ادغام یکبار.
شرمنده ، منظورتون اینه که ۱ فراخوانی به ازای کل عناصر آرایه ولی قسمت دومش رو متوجه نمیشم ، یعنی چی که هر بار ادغام یکبار؟؟؟
ممنون میشم توضیح بیشتر بدین
هر بار که عناصر تک عضوی رو با هم ادغام میکنیم هم یکبار فراخوانی
البته این فراخوانی ها مربوط به رویه merge هستن و نه رویه merge sort .
و نکته ی دیگه ای که داره اگر برای مرتب سازی ادغامی ارایه رو به هر تعداد دسته ( ۲تایی.۵تایی .۱۰ تایی ...) تقسیم کنیم مرتبه این الگوریتم همون nlogn میمونه و تغییر نمیکنه که با تابع زمانیش قابل اثباته.یعنی اگر در تابع زمانی که دوستمون گذاشت به جا ۴ هر عدد دیگه ای بزاریم بازم مرتبه nlogn میشه.