زمان کنونی: ۰۵ آذر ۱۴۰۳, ۰۴:۳۳ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

به دست آوردن مرتبه زمانی( اردر ) یک تابع

ارسال:
  

taranome baran پرسیده:

به دست آوردن مرتبه زمانی( اردر ) یک تابع

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

۱
ارسال:
  

Behnam‌ پاسخ داده:

RE: به دست آوردن مرتبه زمانی( اردر ) یک تابع

(۲۴ مهر ۱۳۹۳ ۰۵:۲۷ ب.ظ)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 رو بدست بیارید)
نقل قول این ارسال در یک پاسخ

ارسال:
  

taranome baran پاسخ داده:

RE: به دست آوردن مرتبه زمانی( اردر ) یک تابع

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

ارسال:
  

Behnam‌ پاسخ داده:

RE: به دست آوردن مرتبه زمانی( اردر ) یک تابع

(۲۶ مهر ۱۳۹۳ ۰۹:۴۴ ق.ظ)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
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

fatemeh69 پاسخ داده:

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] نزدیک می شه
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۴,۹۲۸ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
Smile فروش کتابهای دست دوم و ارزان آمادگی ارشد انفورماتیک پزشکی qizilbash ۱ ۴,۵۸۷ ۲۸ آبان ۱۳۹۹ ۱۱:۳۴ ب.ظ
آخرین ارسال: zeilabi69
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۳۸۸ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۳۴۸ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۳,۰۵۳ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  تابع مولد ss311 ۰ ۱,۴۹۳ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۴۹ ب.ظ
آخرین ارسال: ss311
  مرتبه زمانی Sanazzz ۱۷ ۲۱,۶۴۵ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۷۹۲ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  خرید کتابهای دست دوم پوران پژوهش همه دروس ارشد فناوری اطلاعات sherwod7 ۳ ۵,۷۲۵ ۲۱ دى ۱۳۹۸ ۰۸:۱۶ ب.ظ
آخرین ارسال: roxana.r
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۳,۸۱۶ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close