مسئله بازگشتی T(n)= 8T(n/2) + θ(۱) ; if n^2 > M

سلام.کسی میدونه حل رابطه بازگشتی زیر چی میشه؟

T(n)= 8T(n/2) + θ(۱) -----> if n^2 > M
M ----------------------> if n^2 <= M

توجه:

M یک متغیر مستقل از n است

ارسال: #۲

۱۵ مرداد ۱۳۹۴, ۰۷:۰۰ ق.ظ

Jooybari پاسخ داده:

RE: مسئله بازگشتی سخت!! T(n)= 8T(n/2) + θ(۱) ; if n^2 > M

سلام. وقت بخیر. M یک مقدار ثابته. تاثیر زیادی در فرم کلی رابطه نداره. اگه درخت بازگشت رابطه اول رو بکشید عمق درخت میشه

$k=max(\frac{lgn}{\sqrt{M}},1)$ . سطر آخر درخت بازگشت هم عدد M خواهد بود.
مقدار ثابت هر سطر هم ۸ برابر مقدار ثابت سطر قبلشه. اگه مقدار M رو بزگتر از مقدار ثابت رابطه بگیریم میشه از مقادیر سطرهای میانی صرف نظر کرد. مقدار T با صرف نظر کردن از مقادیر میانی درخت میشه

$T(n)=M\times 8^k$ . برای nهای بزرگ میشه

$T(n)=\frac{3nM}{8^\sqrt{M}}$

ارسال: #۳

۱۹ مرداد ۱۳۹۴, ۰۲:۴۲ ق.ظ

Iranian Wizard پاسخ داده:

RE: مسئله بازگشتی سخت!! T(n)= 8T(n/2) + θ(۱) ; if n^2 > M

(۱۵ مرداد ۱۳۹۴ ۰۷:۰۰ ق.ظ)Jooybari نوشته شده توسط: سلام. وقت بخیر. M یک مقدار ثابته. تاثیر زیادی در فرم کلی رابطه نداره. اگه درخت بازگشت رابطه اول رو بکشید عمق درخت میشه $k=max(\frac{lgn}{\sqrt{M}},1)$ . سطر آخر درخت بازگشت هم عدد M خواهد بود.
مقدار ثابت هر سطر هم ۸ برابر مقدار ثابت سطر قبلشه. اگه مقدار M رو بزگتر از مقدار ثابت رابطه بگیریم میشه از مقادیر سطرهای میانی صرف نظر کرد. مقدار T با صرف نظر کردن از مقادیر میانی درخت میشه $T(n)=M\times 8^k$ . برای nهای بزرگ میشه $T(n)=\frac{3nM}{8^\sqrt{M}}$

ممنونم از اینکه وقت گذاشتین و پاسخ دادین.

موضوع‌های مرتبط با این موضوع...
موضوع:		نویسنده	پاسخ:	بازدید:	آخرین ارسال
	دانلود حل المسائل A First Course in Mathematical Modeling, 5th Edition	jazana	۱	۳,۵۵۵	۱۳ آبان ۱۴۰۱ ۰۱:۲۲ ب.ظ آخرین ارسال: مرجان فهمیده
	کمک به حل مسئله	Moha33	۰	۱,۴۱۹	۰۵ تیر ۱۴۰۰ ۰۹:۴۲ ق.ظ آخرین ارسال: Moha33
	mss در tcp رنو	hashemi15	۴	۴,۸۴۸	۲۴ بهمن ۱۳۹۹ ۱۰:۵۲ ب.ظ آخرین ارسال: hashemi15
	مجموعه تمارین و سوالات امتحانی درس طراحی الگوریتم دانشگاه MIT (سال ۲۰۰۰-۲۰۱۲)	Farid_Feyzi	۵	۸,۱۳۷	۳۰ آبان ۱۳۹۹ ۱۰:۱۵ ب.ظ آخرین ارسال: s-taheri
	رفع اشکال نصب جاوا، مشکل ساخته نشدن virtual machine	shiivaa	۱۲	۲۱,۶۴۱	۱۹ آبان ۱۳۹۹ ۰۷:۲۹ ب.ظ آخرین ارسال: wanted471
	شبیه ساز برای mobile cloud computing؟	samaneh_aftab	۲	۳,۹۹۸	۰۴ اردیبهشت ۱۳۹۹ ۰۱:۰۸ ق.ظ آخرین ارسال: محمد رستمی
	ورود به سایت سامانه همگام – hamgam.medu.ir	edumoshaver1	۰	۲,۲۳۳	۱۲ اسفند ۱۳۹۸ ۰۵:۰۰ ب.ظ آخرین ارسال: edumoshaver1
	کامپیوتر یا هنر، مسئله این است	arian_61	۲	۴,۸۴۳	۲۵ دى ۱۳۹۸ ۱۱:۳۱ ق.ظ آخرین ارسال: packationmachinery
	آموزش msp	rahbar	۰	۲,۱۴۳	۲۳ آبان ۱۳۹۸ ۰۲:۴۳ ب.ظ آخرین ارسال: rahbar
	دانلود رایگان دوره آموزشی PHP & MySQL	SamanehRashvand	۱	۲,۹۶۶	۲۶ مهر ۱۳۹۸ ۰۹:۲۹ ق.ظ آخرین ارسال: alma1988

مسئله بازگشتی T(n)= 8T(n/2) + θ(۱) ; if n^2 > M

مسئله بازگشتی T(n)= 8T(n/2) + θ(۱) ; if n^2 > M

RE: مسئله بازگشتی سخت!! T(n)= 8T(n/2) + θ(۱) ; if n^2 > M

RE: مسئله بازگشتی سخت!! T(n)= 8T(n/2) + θ(۱) ; if n^2 > M

Can I see some ID?

Feeling left out?

رمزت رو فراموش کردی؟

Feeling left out?