محاسبه کارایی الگوریتم بازگشتی انعکاسی؟

[BOB]

سلام

می‌خواستم بدونم روش محاسبه Big O برای الگوریتمهای بازگشتی انعکاسی چگونه است؟

مثلا یه همچین چیزی :




f(n) = 2( f(n) ) + g(n) ;
g(n) = 3( g( n/2 ) ) + 2( f(n) );


O( f(n) ) = ?
O( g(n) ) = ?

[raha_hakhamanesh]

با سلام
معمولا برای بدست آوردن مرتبه زمانی الگوریتم های تودرتو از قواعد اثبات شده در محاسبات مرتبه زمانی الگوریتم ها استفاده می شود . بطور مثال برای نمونه ای که شما ذکر کرده اید باید رشد مرتبه زمانی f,g را در مرحله اول با هم مقایسه کنیم بطور مثال اگر f از مرتبه n و g از مرتبه log n باشد دیگر به حضور g در الگوریتم توجهی نمی کنیم و به سراغ محاسبه مرتبه زمانی f می رویم (این مسئله اثبات شده است. ر ک : تحلیل و طراحی الگوریتم نوشته مهدی جم پور و یا نسخه اصلی : algorithm theory by brasard) .

[BOB]

سلام

آیا دوستان اطلاع دارند که اصلا به اینچین الگوریتمهای بازگشتی (انعکاسی) در زبان انگلیسی چه میگویند ؟؟ اصطلاح خاصی به کار میرود ؟؟
راستش کلمات زیادی رو search کردم ولی هیچکدام مستقیما به چیزی که من میخواستم مربوط نبودند..

موفق باشید

[whitehat]

آیا دوستان اطلاع دارند که اصلا به اینچین الگوریتمهای بازگشتی (انعکاسی) در زبان انگلیسی چه میگویند ؟؟ اصطلاح خاصی به کار میرود ؟؟
Recursive algorithm (http://en.wikipedia.org/wiki/Recursion_%28computer_science%29)
اما برای مورد شما می توانید Recursive Function را جستجو کنید