الگوریتم چندگانه

در علوم کامپیوتر الگوریتم‌های چندگانه در بهینه سازیِ اجرای واقع گرایانه الگوریتم‌های بازگشتی بسیار رایج هستند. به خصوص پیاده‌سازی الگوریتم تقسیم و حل (کاهش و حل) که در آن هر چه به عمق بیشتری در درخت بازگشتی می‌رویم، حجم داده‌ها کاهش می‌یابد. در این حالت یک الگوریتم به عنوان رویکرد کلی در داده‌های بزرگ استفاده می‌شود اما در عمق زیاد درخت بازگشتی به یک الگوریتم دیگر پرش می‌کند که روی داده‌های کوچک‌تر کارآمدتر است. یک مثال رایج این موضوع الگوریتم‌های مرتب‌سازی است. مثلاً مرتب‌سازی درجی که روی داده‌های بزرگ ناکارآمد است اما روی داده‌های کوچک بسیار خوب عمل می‌کند را در نظر بگیرید. برای گام نهایی یعنی بعد از اجرا کردن الگوریتمی دیگر (مانند مرتب‌سازی ادغامی یا مرتب‌سازی سریع) از این نوع مرتب‌سازی استفاده می‌شود چرا که مرتب‌سازی ادغامی و مرتب‌سازی سریع برای داده‌های بزرگ مطلوب هستند ولی سربار قابل توجهی در هنگام استفاده از آن‌ها روی داده‌های کوچک به وجود می‌آید. از این رو از الگوریتمی دیگر در لایه‌های پایین حل بازگشتی استفاده می‌کنند. یک الگوریتم مرتب‌سازی بسیار بهینه الگوریتم مرتب‌سازی تیم است که ترکیبی از مرتب‌سازی ادغامی و مرتب‌سازی درجی به همراه منطق‌های تکمیل‌کننده (از جمله جستجوی دودویی) در منطق ادغام است.

مرتب‌سازی تیم

الگوریتم مرتب‌سازی تیم ترکیبی از دو الگوریتم مرتب‌سازی ادغامی و مرتب‌سازی درجی است. این الگوریتم زیردنباله‌ای را که خودش مرتب است پیدا می‌کند سپس بقیه داده‌ها را مرتب می‌کند و در نهایت با ادغام کردن داده‌های مرتب اولیه و داده‌مرتب شده کل داده‌ها در زمان سریع‌تری مرتب می‌شوند. این الگوریتم در بهترین حالت یک مجموعه داده را در زمان خطی و در حالت متوسط و بدترین حالت مجموعه با ${\displaystyle n}$

حالت اولیه کوتاه شده

یک روش کلی برای یک الگوریتم بازگشتی چندگانه حالت اولیه کوتاه شده‌است. در این روش این که در گام بعدی حالت اولیه اجرا می‌شود یا خیر پیش از فراخوانی تابع بررسی می‌شود که این موجب جلوگیری از فراخوانی تابع‌های غیرضروری می‌شود. برای مثال در یک درخت به جای صدا زدن تابع روی یک فرزند و سپس چک کردن اینکه آن فرزند ${\displaystyle NULL}$

مرتب‌سازی درونگرا

مثال دیگر از الگوریتم‌های چندگانه و نحوه عملکرد آن‌ها مرتب‌سازی درونگرا و انتخاب درونگرا است که یک الگوریتم سریع برای حالت میانگین و الگوریتمی دیگر برای بهینه شدن بدترین حالت را ترکیب می‌کنند. مرتب‌سازی درونگرا با مرتب‌سازی سریع آغاز می‌شود و در ادامه با زیاد شدن عمق درخت بازگشتی الگوریتم به مرتب‌سازی هرمی تغییر می‌کند. این باعث می‌شود مرتب‌سازی درونگرا در بدترین حالت از مرتبه زمانی ${\displaystyle O(nlogn)}$

اما در برخی پیاده‌سازی‌های مرتب‌سازی درونگرا در مرحله پایانی و پس از اجرای مرتب‌سازی هرمی، مرتب‌سازی درجی استفاده می‌شود. برای درک بهتر در ادامه گام‌های مرتب‌سازی درونگرا را بررسی می‌کنیم:

• ابتدا یک بخش را جدا می‌کنیم. سه حالت پیش می‌آید:

• اگر تعداد عناصر بخش جدا شده از حدی که از پیش معین شده(${\displaystyle 2\ast logn}$
  ) بیشتر باشد روی این بخش مرتب‌سازی هرمی پیاده می‌شود.
• اگر تعداد عناصر این بخش از ${\displaystyle 16}$
  کمتر باشد روی این بخش مرتب‌سازی درجی را پیاده می‌کنیم. (عدد ۱۶ با محاسبات به‌دست آمده‌است)
• در غیراینصورت روی بخش جدا شده مرتب‌سازی سریع را اعمال می‌کنیم.

الگوریتم‌های توزیع شده

از الگوریتم‌های توزیع شده متمرکز اغلب به عنوان الگوریتم‌های چندگانه یاد می‌شود زیرا این الگوریتم‌ها متشکل از یک الگوریتم تکی (اجرا بر روی هر پردازنده توزیع شده) و یک الگوریتم ترکیبی (اجرا روی متمرکزکننده توزیع) هستند. یک مثال اولیه از این الگوریتم‌ها مرتب‌سازی توزیعی است که مخصوصاً برای مرتب‌سازی خارجی استفاده می‌شود که همه داده‌ها را به زیر مجموعه‌های جدا از هم تقسیم می‌کند، هر زیر مجموعه را مرتب می‌کند و در نهایت زیر مجموعه‌ها را ترکیب می‌کند تا داده‌های مرتب شده حاصل شوند. مشابه مرتب‌سازی سطلی مرتب و مرتب‌سازی فلش.

اما به‌طور کلی الگوریتم‌های توزیع شده الزاماً الگوریتم‌های چندگانه نیستند چرا که الگوریتم‌های تکی یا ترکیب چند الگوریتم به هر حال ممکن است چند مسئله مختلف را حل کند. برای مثال در مدل‌هایی مانند نگاشت کاهش گام نگاشت و گام کاهش مسئله‌های مختلفی را حل می‌کنند و با هم ترکیب می‌شوند تا مسئله متفاوت سومی را حل کنند.

• مرتب‌سازی تیم
• توابع بازگشتی
• مرتب‌سازی درونگرا