(۲۴ مهر ۱۳۹۳ ۰۵:۲۷ ب.ظ)taranome baran نوشته شده توسط:  سلام دوستان

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

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

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

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

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

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