حل رابطه

[iranch]

با درود
عزیزان این رابطه که ظاهرا بازگشتی هست چطور حل شده؟ خط اول از1 +3 صرف نظر میکنیم به دلایلی.

[paveej]

درود

با توجه به سه رابطه اول ميشه رابطه چهارم رو نتيجه گرفت:

T(n)=2T(n/2)+n

T(n)=2²T(n/2²)+2n

T(n)=2³T(n/2³)+3n
.
.
.
T(n)=2ªT(n/2ª)+a.n

حالا اگه فرض كنيم n=2ª مقدار a برابر a=log n ميشه.البته مبناي لگاريتم در اينجا 2 هست.با قرار دادن a=log n در رابطه آخر فرمول گفته شده بدست مياد.