تصادفی در مقابل الگوریتم بازگشتی
الگوریتم های تصادفی شده با انتخاب های تصادفی در طول اجرای الگوریتم، حس تصادفی بودن را در منطق خود گنجانده اند. به دلیل این تصادفی بودن، رفتار الگوریتم می تواند حتی برای یک ورودی ثابت تغییر کند. برای بسیاری از مسائل، الگوریتم های تصادفی ساده ترین و کارآمدترین راه حل ها را ارائه می دهند. الگوریتم های بازگشتی مبتنی بر این ایده هستند که راه حل یک مسئله را می توان با یافتن راه حل برای مسائل فرعی کوچکتر همان مسئله پیدا کرد. بازگشت به طور گسترده ای برای یافتن راه حل برای مشکلات در علوم کامپیوتر استفاده می شود و بسیاری از زبان های برنامه نویسی سطح بالا از بازگشت استفاده می کنند.
الگوریتم تصادفی چیست؟
الگوریتم های تصادفی شده با انتخاب های تصادفی که اجرای الگوریتم را هدایت می کند، حس تصادفی بودن را در خود جای می دهند. این معمولاً با گرفتن مجموعه ای از اعداد تصادفی تولید شده توسط یک مولد اعداد شبه تصادفی به عنوان ورودی اضافی انجام می شود. به همین دلیل، رفتار الگوریتم ممکن است حتی برای یک ورودی ثابت تغییر کند. Quicksort یک الگوریتم بسیار شناخته شده است که از مفهوم تصادفی بودن استفاده می کند و بدون در نظر گرفتن ویژگی های ورودی، زمان اجرای O(n log n) دارد. علاوه بر این، روش ساخت و ساز افزایشی تصادفی برای سازه های ساختمانی مانند بدنه محدب در هندسه محاسباتی استفاده می شود. در این روش، نقاط ورودی به صورت تصادفی جابه‌جا می‌شوند و سپس یکی یکی به ساختار وارد می‌شوند. پیاده‌سازی یک الگوریتم تصادفی نسبتاً ساده از اجرای یک الگوریتم قطعی برای همان مسئله است. بزرگترین چالش در طراحی یک الگوریتم تصادفی در انجام تحلیل مجانبی برای پیچیدگی زمان و مکان نهفته است.
الگوریتم بازگشتی چیست؟
الگوریتم های بازگشتی بر این ایده مبتنی هستند که راه حل یک مسئله را می توان با یافتن راه حل برای مسائل فرعی کوچکتر همان مسئله پیدا کرد. در یک الگوریتم بازگشتی، یک تابع بر اساس نسخه قبلی خود تعریف می شود. توجه به این نکته مهم است که این خود ارجاع باید یک شرط خاتمه داشته باشد تا برای همیشه از ارجاع به خود جلوگیری کند. شرایط خاتمه قبل از ارجاع به خود بررسی می شود. مرحله اولیه یک الگوریتم بازگشتی به بند پایه تعریف بازگشتی مسئله مربوط می شود. مراحلی که از مرحله اولیه پیروی می کنند، مربوط به بندهای استقرایی مسئله است. الگوریتم‌های بازگشتی راه‌حل ساده‌تری را در بسیاری از موقعیت‌ها ارائه می‌کنند و نسبت به الگوریتم تکراری برای همان مسئله به روش طبیعی تفکر نزدیک‌تر است. اما به طور کلی، الگوریتم های بازگشتی به حافظه بیشتری نیاز دارند و از نظر محاسباتی گران هستند.
تفاوت بین الگوریتم تصادفی و بازگشتی چیست؟
الگوریتم‌های تصادفی الگوریتم‌هایی هستند که با انتخاب‌های تصادفی که می‌توانند بر اجرای الگوریتم تأثیر بگذارند، از حس تصادفی بودن استفاده می‌کنند، در حالی که الگوریتم‌های بازگشتی الگوریتم‌هایی هستند که مبتنی بر این ایده هستند که می‌توان با یافتن راه‌حلی برای یک مسئله پیدا کرد. راه حل برای مسائل فرعی کوچکتر همان مسئله. با توجه به تصادفی بودن الگوریتم های تصادفی، رفتار الگوریتم می تواند حتی برای همان ورودی (در اجراهای مختلف الگوریتم) تغییر کند. اما این در الگوریتم های بازگشتی امکان پذیر نیست و رفتار یک الگوریتم بازگشتی برای یک ورودی ثابت یکسان خواهد بود.
