(۲۱ دى ۱۳۹۲ ۱۰:۲۸ ق.ظ)amin222 نوشته شده توسط:  سلام
دوستان کسی میتونه راجع به بدست اوردن مرتبه زمانی رابطه زیر کمکی کنه
$T(n)=2T(n/2) T(3n/4) n$
جوابش هم
$T(n)=O(n^2)$

سلام دوست عزیز
از درخت بازگشت استفاده میکنیم:
n
n/2 3n/4
n/4 3n/8 9n/16 3n/8
و ...
جمع سطر اول: n
جمع سطر دوم: ۵n/4
جمع سطر سوم: ۲۵n/16
همانطور که میبینید یک دنباله هندسی داریم با q=5/4 و تعداد عناصر این دنباله یا همون تعداد سطر ها لوگاریتم n برمبنای ۴/۳ هست. مجموع این دنباله ۲^n میشود.

دوست عزیز ممنونم از پاسختون
ولی اشکال من همین تکیه آخر بقول شما ما لگاریتم n بر مبنای ۴/۳ سطر داریم
یعنی باید لگاریتم n بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم

(۲۱ دى ۱۳۹۲ ۰۱:۲۳ ب.ظ)amin222 نوشته شده توسط:  دوست عزیز ممنونم از پاسختون
ولی اشکال من همین تکیه آخر بقول شما ما لگاریتم n بر مبنای ۴/۳ سطر داریم
یعنی باید لگاریتم n بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم

خواهش میکنم ، من تصویر رو نتونستم ببینم خطا میده (نمیدونم چرا بعضی اوقات اینطوری میشه) ولی برای محاسبه مجموع سری هندسی در قسمتی که q به توان لگاریتم n برمبنای ۴/۳ هست از فرمول زیر استفاده کنید:

$\frac{5}{4}^{log_\frac{4}{3}{n}} = n^{log_\frac{4}{3}{\frac{5}{4}}}$

که مقدار بالا به طور تقریبی برایرست با: $n^{1}$
که در نهایت مجموع سری از مرتبه $n^{2}$ میباشد.

(۲۱ دى ۱۳۹۲ ۰۳:۵۵ ب.ظ)misagh01 نوشته شده توسط:  

(21 دى ۱۳۹۲ ۰۱:۲۳ ب.ظ)amin222 نوشته شده توسط:  دوست عزیز ممنونم از پاسختون
ولی اشکال من همین تکیه آخر بقول شما ما لگاریتم n بر مبنای ۴/۳ سطر داریم
یعنی باید لگاریتم n بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم

خواهش میکنم ، من تصویر رو نتونستم ببینم خطا میده (نمیدونم چرا بعضی اوقات اینطوری میشه) ولی برای محاسبه مجموع سری هندسی در قسمتی که q به توان لگاریتم n برمبنای ۴/۳ هست از فرمول زیر استفاده کنید:

$\frac{5}{4}^{log_\frac{4}{3}{n}} = n^{log_\frac{4}{3}{\frac{5}{4}}}$

که مقدار بالا به طور تقریبی برایرست با: $n^{1}$
که در نهایت مجموع سری از مرتبه $n^{2}$ میباشد.

دستت درد نکنه گرفتم چی شد واقعا ممنون

سلام دوستان، مگه توصورت سوال نگفته(۲T(n/2؟ پس چرا تودرخت بازگشتی n/2 رو یکبار لحاظ کردین؟؟

(۲۳ دى ۱۳۹۲ ۱۰:۰۶ ب.ظ)raziiiiiiiiiiie نوشته شده توسط:  سلام دوستان، مگه توصورت سوال نگفته(۲T(n/2؟ پس چرا تودرخت بازگشتی n/2 رو یکبار لحاظ کردین؟؟

فکر کنم دوستمون از قلام انداخته ولی درست هست محاسباتش

(۲۳ دى ۱۳۹۲ ۱۰:۰۶ ب.ظ)raziiiiiiiiiiie نوشته شده توسط:  سلام دوستان، مگه توصورت سوال نگفته(۲T(n/2؟ پس چرا تودرخت بازگشتی n/2 رو یکبار لحاظ کردین؟؟

سلام
فکر میکنم حق با شماست، ممنون از تذکرتون. با احتساب ۲ بار n/2 فرمول زیر تغییر میکنه :

$\frac{5}{4}^{log_\frac{4}{3}{n}} = n^{log_\frac{4}{3}{\frac{5}{4}}}$

تبدیل میشه به:

$\frac{7}{4}^{log_\frac{4}{3}{n}} = n^{log_\frac{4}{3}{\frac{7}{4}}} \simeq n^{1}$

که در نهایت جواب مجموع سری هندسی با فرمول بالا میشه همون $n^{2}$ .