تالار گفتمان مانشت
به دست آوردن مرتبه زمانی( اردر ) یک تابع - نسخه‌ی قابل چاپ
به دست آوردن مرتبه زمانی( اردر ) یک تابع - taranome baran - 24 مهر ۱۳۹۳ ۰۵:۲۷ ب.ظ

سلام دوستان
[تصویر: l7s2uzfrlgu0.png][/quote][/code]
کسی میدونه چطوری میشه اینجور مثال ها را حل کرد؟
تنها چیزی که وجود داره اینه که n در هر مرحله دو برابر شده ولی بین زمان های اجرا هیچ رابطه ای وجود نداره.HuhHuh
کسی میتونه راهنماییم کنه؟
مرسی

RE: به دست آوردن مرتبه زمانی( اردر ) یک تابع - taranome baran - 25 مهر ۱۳۹۳ ۱۰:۴۴ ق.ظ

آخه برای این مثال با روش های درون یابی محاسبات خیلی زیاد پیچیده و طولانی میشه مثلا اگه بخوام از لاگرانژ استفاده کنم محاسبات خیلی وحشتناک میشه . هیچ روش دیگه ای وجود نداره؟

RE: به دست آوردن مرتبه زمانی( اردر ) یک تابع - fatemeh69 - 25 مهر ۱۳۹۳ ۱۱:۱۵ ب.ظ

مسلما رشد تابع از n کمتره از logn هم بیشتره چون log عدد آخر در مبنای ۱۰ میشه ۶ در مبنای عدد نپر می شه ۱۴ و کلا با هر مبنای دیگه یه چیزی تو این مایه هاست
پس باید به مرتبه هایی فکر کنیم که بین n و logn باشند مثلا رادیکالی ها:
اگر از اعداد رادیکال بگیریم:
[tex]\sqrt{524288}=724.07[/tex]
[tex]\sqrt{1048576}=1024[/tex]
[tex]\sqrt{2097152}=1448.15[/tex]
اگه دقت کنید در این سه تایی که نوشتم در اولی خروجی ما تقربا ۷ برابر خروجی داده شده است
در دومی تقریبا ۲/۵ برابر و در سومی تقریبا برابر است این نشان می ده که رشد تابع داره به رشد [tex]\sqrt{n}[/tex] نزدیک می شه

RE: به دست آوردن مرتبه زمانی( اردر ) یک تابع - Behnam‌ - ۲۶ مهر ۱۳۹۳ ۰۲:۳۱ ق.ظ

(۲۴ مهر ۱۳۹۳ ۰۵:۲۷ ب.ظ)taranome baran نوشته شده توسط:  سلام دوستان
[تصویر: l7s2uzfrlgu0.png]
[/code]
کسی میدونه چطوری میشه اینجور مثال ها را حل کرد؟
تنها چیزی که وجود داره اینه که n در هر مرحله دو برابر شده ولی بین زمان های اجرا هیچ رابطه ای وجود نداره.HuhHuh
کسی میتونه راهنماییم کنه؟
مرسی
[/quote]

رشد تابع برابر با n به توان ۱/۸۹ یا به طور دقیق‌تر، n به توان ۱/۸۸۸ هست.
اگر شما اعداد ستون دوم رو به عدد قبلی تقسیم کنید، به ۳/۷ میل می‌کنه، مخصوصاً در عدد‌های آخری. در نتیجه میشه نوشت که (T(2n)=3.7*T(n
و حل این میشه T(2n)=n^1.888، در نتیجه (T(n هم همون میشه.
البته اگه اعداد سمت چپ رو به جای n قرار بدید عدد خیلی بزرگتر نسبت به سلول سمت راست به دست میاد، ولی مرتبه همین هست. باید در یه ضریب c خیلی کوچیکی ضرب کنید تا همون عدد سمت چپ بدست بیاد که این ضریب حدود ۱/۷۳۳۳ ضربدر ۱۰ به توان منهای ۹ هست (کافیه یکی از اعداد سمت چپ رو به جای n قرار بدید و c رو بدست بیارید)

RE: به دست آوردن مرتبه زمانی( اردر ) یک تابع - taranome baran - 26 مهر ۱۳۹۳ ۰۹:۴۴ ق.ظ

ممنون از پاسختون فقط یه سوال :
[tex]T(2n)=3.7T(n)[/tex]
را چطوری [tex]n^{1.888}[/tex] به دست آوردید؟

RE: به دست آوردن مرتبه زمانی( اردر ) یک تابع - Behnam‌ - ۲۶ مهر ۱۳۹۳ ۰۴:۵۶ ب.ظ

(۲۶ مهر ۱۳۹۳ ۰۹:۴۴ ق.ظ)taranome baran نوشته شده توسط:  ممنون از پاسختون فقط یه سوال :
[tex]T(2n)=3.7T(n)[/tex]
را چطوری [tex]n^{1.888}[/tex] به دست آوردید؟

T(2n)=3.7T(n)=3.7*(3.7T(n/2))=3.7*3.7*3.7T(n/4)=...=3.7^lg(n)=n^lg(3.7)=n^1.887