۰
subtitle
ارسال: #۱
  
به دست آوردن مرتبه زمانی( اردر ) یک تابع
سلام دوستان
[/quote][/code]
کسی میدونه چطوری میشه اینجور مثال ها را حل کرد؟
تنها چیزی که وجود داره اینه که n در هر مرحله دو برابر شده ولی بین زمان های اجرا هیچ رابطه ای وجود نداره.
کسی میتونه راهنماییم کنه؟
مرسی
[/quote][/code]
کسی میدونه چطوری میشه اینجور مثال ها را حل کرد؟
تنها چیزی که وجود داره اینه که n در هر مرحله دو برابر شده ولی بین زمان های اجرا هیچ رابطه ای وجود نداره.
کسی میتونه راهنماییم کنه؟
مرسی
۱
ارسال: #۲
  
RE: به دست آوردن مرتبه زمانی( اردر ) یک تابع
(۲۴ مهر ۱۳۹۳ ۰۵:۲۷ ب.ظ)taranome baran نوشته شده توسط: سلام دوستان[/code]
کسی میدونه چطوری میشه اینجور مثال ها را حل کرد؟
تنها چیزی که وجود داره اینه که n در هر مرحله دو برابر شده ولی بین زمان های اجرا هیچ رابطه ای وجود نداره.
کسی میتونه راهنماییم کنه؟
مرسی
[/quote]
رشد تابع برابر با n به توان ۱/۸۹ یا به طور دقیقتر، n به توان ۱/۸۸۸ هست.
اگر شما اعداد ستون دوم رو به عدد قبلی تقسیم کنید، به ۳/۷ میل میکنه، مخصوصاً در عددهای آخری. در نتیجه میشه نوشت که (T(2n)=3.7*T(n
و حل این میشه T(2n)=n^1.888، در نتیجه (T(n هم همون میشه.
البته اگه اعداد سمت چپ رو به جای n قرار بدید عدد خیلی بزرگتر نسبت به سلول سمت راست به دست میاد، ولی مرتبه همین هست. باید در یه ضریب c خیلی کوچیکی ضرب کنید تا همون عدد سمت چپ بدست بیاد که این ضریب حدود ۱/۷۳۳۳ ضربدر ۱۰ به توان منهای ۹ هست (کافیه یکی از اعداد سمت چپ رو به جای n قرار بدید و c رو بدست بیارید)
ارسال: #۳
  
RE: به دست آوردن مرتبه زمانی( اردر ) یک تابع
ممنون از پاسختون فقط یه سوال :
[tex]T(2n)=3.7T(n)[/tex]
را چطوری [tex]n^{1.888}[/tex] به دست آوردید؟
[tex]T(2n)=3.7T(n)[/tex]
را چطوری [tex]n^{1.888}[/tex] به دست آوردید؟
ارسال: #۴
  
RE: به دست آوردن مرتبه زمانی( اردر ) یک تابع
۰
ارسال: #۵
  
RE: به دست آوردن مرتبه زمانی( اردر ) یک تابع
مسلما رشد تابع از 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] نزدیک می شه
پس باید به مرتبه هایی فکر کنیم که بین n و logn باشند مثلا رادیکالی ها:
اگر از اعداد رادیکال بگیریم:
[tex]\sqrt{524288}=724.07[/tex]
[tex]\sqrt{1048576}=1024[/tex]
[tex]\sqrt{2097152}=1448.15[/tex]
اگه دقت کنید در این سه تایی که نوشتم در اولی خروجی ما تقربا ۷ برابر خروجی داده شده است
در دومی تقریبا ۲/۵ برابر و در سومی تقریبا برابر است این نشان می ده که رشد تابع داره به رشد [tex]\sqrt{n}[/tex] نزدیک می شه
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close