سلام
دوستان کسی میتونه راجع به بدست اوردن مرتبه زمانی رابطه زیر کمکی کنه
[tex]T(n)=2T(n/2) T(3n/4) n[/tex]
جوابش هم
[tex]T(n)=O(n^2)[/tex]
(۲۱ دى ۱۳۹۲ ۱۰:۲۸ ق.ظ)amin222 نوشته شده توسط: سلام
دوستان کسی میتونه راجع به بدست اوردن مرتبه زمانی رابطه زیر کمکی کنه
[tex]T(n)=2T(n/2) T(3n/4) n[/tex]
جوابش هم
[tex]T(n)=O(n^2)[/tex]
سلام دوست عزیز
از درخت بازگشت استفاده میکنیم:
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 بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم
[attachment=14586]
(۲۱ دى ۱۳۹۲ ۰۱:۲۳ ب.ظ)amin222 نوشته شده توسط: دوست عزیز ممنونم از پاسختون
ولی اشکال من همین تکیه آخر بقول شما ما لگاریتم n بر مبنای ۴/۳ سطر داریم
یعنی باید لگاریتم n بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم
خواهش میکنم
، من تصویر رو نتونستم ببینم خطا میده (نمیدونم چرا بعضی اوقات اینطوری میشه) ولی برای محاسبه مجموع سری هندسی در قسمتی که q به توان لگاریتم n برمبنای ۴/۳ هست از فرمول زیر استفاده کنید:[tex]\frac{5}{4}^{log_\frac{4}{3}{n}} = n^{log_\frac{4}{3}{\frac{5}{4}}}[/tex]
که مقدار بالا به طور تقریبی برایرست با: [tex]n^{1}[/tex]
که در نهایت مجموع سری از مرتبه [tex]n^{2}[/tex] میباشد.
(۲۱ دى ۱۳۹۲ ۰۳:۵۵ ب.ظ)misagh01 نوشته شده توسط:(21 دى ۱۳۹۲ ۰۱:۲۳ ب.ظ)amin222 نوشته شده توسط: دوست عزیز ممنونم از پاسختون
ولی اشکال من همین تکیه آخر بقول شما ما لگاریتم n بر مبنای ۴/۳ سطر داریم
یعنی باید لگاریتم n بر مبنای ۴/۳ جمله اول یک تصاعد هندسی با قدر نسبت ۵/۴ رو حساب کنیم درسته؟این عکسرو ببینید مشکل من اینجاست که علامت سوال گذاشتم بنظرم یه مشکل ریاضی دارم
خواهش میکنم
[tex]\frac{5}{4}^{log_\frac{4}{3}{n}} = n^{log_\frac{4}{3}{\frac{5}{4}}}[/tex]
که مقدار بالا به طور تقریبی برایرست با: [tex]n^{1}[/tex]
که در نهایت مجموع سری از مرتبه [tex]n^{2}[/tex] میباشد.
دستت درد نکنه گرفتم چی شد واقعا ممنون
سلام دوستان، مگه توصورت سوال نگفته(۲T(n/2؟ پس چرا تودرخت بازگشتی n/2 رو یکبار لحاظ کردین؟؟
(۲۳ دى ۱۳۹۲ ۱۰:۰۶ ب.ظ)raziiiiiiiiiiie نوشته شده توسط: سلام دوستان، مگه توصورت سوال نگفته(۲T(n/2؟ پس چرا تودرخت بازگشتی n/2 رو یکبار لحاظ کردین؟؟
فکر کنم دوستمون از قلام انداخته ولی درست هست محاسباتش
(۲۳ دى ۱۳۹۲ ۱۰:۰۶ ب.ظ)raziiiiiiiiiiie نوشته شده توسط: سلام دوستان، مگه توصورت سوال نگفته(۲T(n/2؟ پس چرا تودرخت بازگشتی n/2 رو یکبار لحاظ کردین؟؟
سلام
فکر میکنم حق با شماست، ممنون از تذکرتون. با احتساب ۲ بار n/2 فرمول زیر تغییر میکنه :
[tex]\frac{5}{4}^{log_\frac{4}{3}{n}} = n^{log_\frac{4}{3}{\frac{5}{4}}}[/tex]
تبدیل میشه به:
[tex]\frac{7}{4}^{log_\frac{4}{3}{n}} = n^{log_\frac{4}{3}{\frac{7}{4}}} \simeq n^{1}[/tex]
که در نهایت جواب مجموع سری هندسی با فرمول بالا میشه همون [tex]n^{2}[/tex] .