الگوریتم های بازگشتی یک مفهوم اساسی در علوم کامپیوتر هستند.آنها با شکستن آنها به مشکلات کوچکتر و مشابه حل می کنند. درک پیچیدگی زمان آنها به ارزیابی کارایی و عملکرد آنها کمک می کند.

پیچیدگی زمان چیست؟

پیچیدگی زمان اندازه گیری می کند که چگونه زمان اجرای یک الگوریتم با اندازه ورودی افزایش می یابد.این با استفاده از لوسیون بزرگ O بیان می شود که محدوده بالایی از نرخ رشد الگوریتم را توصیف می کند.

تحلیل الگوریتم های بازگشتی

الگوریتم های بازگشتی اغلب شامل حل یک مشکل با تماس با همان تابع با ورودی های کوچکتر است.برای تجزیه و تحلیل پیچیدگی زمان خود، ضروری است که رابطه عود را درک کنیم که کل زمان را بر اساس مشکلات کوچک زیر نشان می دهد.

روش های معمول برای محاسبه

دو روش اولیه برای حل روابط عود استفاده می شود:

  • روش فرعی: حدس بزنید راه حل و تأیید آن از طریق القا.
  • روش درخت بازگشتی: تجسم بازگشت به عنوان یک درخت به خلاصه هزینه در هر سطح.

به عنوان مثال، عود T(n) = 2T (n/2) + n یک الگوریتم تقسیم و-کانر را توصیف می کند.بنابراین حل این امر به یک پیچیدگی زمانی O(n log n) می پردازد.