با سلام.در بعض مسائل با وجود نزدیکی اندازه زیرمسائل به اندازه مسئله اصلی ممکنه که روش تقسیم و حل مناسب و بهینه باشه؟
الگوریتم محاسبه فاکتوریل n از مرتبه [tex]O(n)[/tex] هست که مناسبه.
فکر میکنم علتش این باشه که زیر مسائل با یکدیگه همپوشانی ندارند!درست عرض میکنم؟
بله چون توی بازگشتی‌ها ذخیره صورت نمیگیره و ممکنه یه تابع به ازای یک مقدار خاص چندین بار حساب بشه. مثل فیبوناچی
معمولاً اگه اندازه زیر مسائل اندازه مسئله اصلی باشه، روش تقسیم و غلبه مناسب نیست مگه اینکه تعداد زیر مسائل کم و هزینه ترکیب مسائل کوچک باشد. مثلاً
[tex]T(n) = t(n-1) O(1)[/tex]
تابع فوق از مرتبه [tex]n[/tex] هست.
البته دلیل اصلی کم بودن پیچیدگی همون عدم همپوشانی فضای حالت است نه کوچک بودن هزینه ترکیب.
مثال خوب این مساله هم همون فیبوناتچی است. هزینه ترکیب فیبوناتچی هم [tex]O(1) [/tex] هست ولی هزینه کلی چیز وحشتناکیه. دلیل اصلیش هم چند بار محاسبه جواب‍های مساله است. در مورد این نوع مسایل بهترین الگوریتم‍ها معمولاً الگوریتم‍های دارای حافظه مثل الگوریتم‍های پویا هستند. البته در این شرایط باید پیچیدگی حافظه رو هم محاسبه کرد. برخی اوقات پیچیدگی حافظه خودش بلای جون می‍شه!!