زمینه
هنگام مواجهه با مشکلات بازگشتی ، ما به سرعت تقویت یادآوری را برای جلوگیری از هدر رفتن چرخه برای محاسبات گذشته شناسایی می کنیم. اما در مورد پیاده سازی های اساسی از بالا به پایین در مقابل از پایین به بالا چیست؟
در ویدیوی زیر این دو را مقایسه می کنم. و اشکالاتی در استفاده از BFS در این مورد خاص:
- استفاده از حافظه بالاتر به دلیل حفظ صف و الف مورد بازدید مجموعه
- بدتر از DP برای بزرگ مقدار مقادیر (از آنجا که BFS سطح را بر اساس سطح بررسی می کند ، می تواند برای مقادیر زیاد آهسته باشد).
خلاصه
نمایش بصری
مقایسه
| رویکرد | پیچیدگی زمانی | پیچیدگی فضا | یادداشت ها |
|---|---|---|---|
| DP بازگشتی (از بالا به پایین W/ Memoization) | o (مقدار × لن (سکه)) | o (مقدار) | کارآمد ، اما بازگشت از حافظه پشته استفاده می کند |
| DP تکراری (پایین به بالا) | o (مقدار × لن (سکه)) | o (مقدار) | بهترین برای پوشش زیرنویس متراکم |
| BFS (نمودار نمودار) | o (مقدار × لن (سکه)) (بدترین حالت) | o (مقدار) | می تواند برای مقادیر کوچک کارآمدتر باشد |
