سلام.کسی میدونه حل رابطه بازگشتی زیر چی میشه؟
T(n)= 8T(n/2) + θ(۱) -----> if n^2 > M
M ----------------------> if n^2 <= M
M ----------------------> if n^2 <= M
توجه:
M یک متغیر مستقل از n است
سلام. وقت بخیر. M یک مقدار ثابته. تاثیر زیادی در فرم کلی رابطه نداره. اگه درخت بازگشت رابطه اول رو بکشید عمق درخت میشه [tex]k=max(\frac{lgn}{\sqrt{M}},1)[/tex]. سطر آخر درخت بازگشت هم عدد M خواهد بود.
مقدار ثابت هر سطر هم ۸ برابر مقدار ثابت سطر قبلشه. اگه مقدار M رو بزگتر از مقدار ثابت رابطه بگیریم میشه از مقادیر سطرهای میانی صرف نظر کرد. مقدار T با صرف نظر کردن از مقادیر میانی درخت میشه [tex]T(n)=M\times 8^k[/tex]. برای nهای بزرگ میشه [tex]T(n)=\frac{3nM}{8^\sqrt{M}}[/tex]
(۱۵ مرداد ۱۳۹۴ ۰۷:۰۰ ق.ظ)Jooybari نوشته شده توسط: سلام. وقت بخیر. M یک مقدار ثابته. تاثیر زیادی در فرم کلی رابطه نداره. اگه درخت بازگشت رابطه اول رو بکشید عمق درخت میشه [tex]k=max(\frac{lgn}{\sqrt{M}},1)[/tex]. سطر آخر درخت بازگشت هم عدد M خواهد بود.
مقدار ثابت هر سطر هم ۸ برابر مقدار ثابت سطر قبلشه. اگه مقدار M رو بزگتر از مقدار ثابت رابطه بگیریم میشه از مقادیر سطرهای میانی صرف نظر کرد. مقدار T با صرف نظر کردن از مقادیر میانی درخت میشه [tex]T(n)=M\times 8^k[/tex]. برای nهای بزرگ میشه [tex]T(n)=\frac{3nM}{8^\sqrt{M}}[/tex]
ممنونم از اینکه وقت گذاشتین و پاسخ دادین.