۰
subtitle
ارسال: #۱
  
مرتبه زمانی این تابع چی میشه ؟
سلام دوستان
میشه بگید مرتبه زمانی این تابع چی میشه ؟
[tex]f(n)=\frac{1}{2}f(\frac{n}{2}) 1[/tex]
میشه بگید مرتبه زمانی این تابع چی میشه ؟
[tex]f(n)=\frac{1}{2}f(\frac{n}{2}) 1[/tex]
۰
ارسال: #۲
  
RE: مرتبه زمانی این تابع چی میشه ؟
سلام من از راه بسط دادن به به جواب اوی۱ رسیدم
که به نظرم منطقی هم هست چون هر بار جواب ،برابر جواب نصف مقادیر اصلی تقسیم بر دو میشه یعنی تقریبا هیچ !
اگه در یک دوم ضرب نمیشد ، یک ها log nبار جمع میشدن و lognجواب بود اما حالا نصف میشن ودر نهایت چیزی در حدود ۲ میشه
ببخشید کیبورد مناسب نداشتم وگرنه توی texجواب میدادم
باقی دوستان چه نظری دارند
که به نظرم منطقی هم هست چون هر بار جواب ،برابر جواب نصف مقادیر اصلی تقسیم بر دو میشه یعنی تقریبا هیچ !
اگه در یک دوم ضرب نمیشد ، یک ها log nبار جمع میشدن و lognجواب بود اما حالا نصف میشن ودر نهایت چیزی در حدود ۲ میشه
ببخشید کیبورد مناسب نداشتم وگرنه توی texجواب میدادم
باقی دوستان چه نظری دارند
۰
ارسال: #۳
  
RE: مرتبه زمانی این تابع چی میشه ؟
بنظر شما دوستان اگه این عبارت معرف تابع T باشه آیا صورت این عبارت زمانی درسته؟
آخه من ندیدم که تایم معادله بازگشتی روبه صورت نصف تایم قبلی تعریف کنیم. چون در این صورت تابع ما دیگه بازگشتی نداره.
دقیق تر اینکه ضریب تابع زمان بازگشتی باید ۱ یا عدد صحیح بزرگتر ۱ باشه تا بتونیم بگیم که تابع ما چند بار در هر مرحله بازگشت خورده !!!
پ.ن : اگر که این سوال صورت دقیق همون تابع F باشه و بخوایم تابع T اون رو استخراج و سپس حل کنیم براحتی مشخصه که Logn میشه
آخه من ندیدم که تایم معادله بازگشتی روبه صورت نصف تایم قبلی تعریف کنیم. چون در این صورت تابع ما دیگه بازگشتی نداره.
دقیق تر اینکه ضریب تابع زمان بازگشتی باید ۱ یا عدد صحیح بزرگتر ۱ باشه تا بتونیم بگیم که تابع ما چند بار در هر مرحله بازگشت خورده !!!
پ.ن : اگر که این سوال صورت دقیق همون تابع F باشه و بخوایم تابع T اون رو استخراج و سپس حل کنیم براحتی مشخصه که Logn میشه
ارسال: #۴
  
RE: مرتبه زمانی این تابع چی میشه ؟
(۲۰ مرداد ۱۳۹۳ ۰۶:۲۲ ب.ظ)ADELZX نوشته شده توسط: بنظر شما دوستان اگه این عبارت معرف تابع T باشه آیا صورت این عبارت زمانی درسته؟باهاتون موافقم ۱/۲ بار بازگشت کردن معنی نداره!
آخه من ندیدم که تایم معادله بازگشتی روبه صورت نصف تایم قبلی تعریف کنیم. چون در این صورت تابع ما دیگه بازگشتی نداره.
دقیق تر اینکه ضریب تابع زمان بازگشتی باید ۱ یا عدد صحیح بزرگتر ۱ باشه تا بتونیم بگیم که تابع ما چند بار در هر مرحله بازگشت خورده !!!
پ.ن : اگر که این سوال صورت دقیق همون تابع F باشه و بخوایم تابع T اون رو استخراج و سپس حل کنیم براحتی مشخصه که Logn میشه
۰
ارسال: #۵
  
RE: مرتبه زمانی این تابع چی میشه ؟
سلام.شما وقتی این رابطه رو تا آخر باز کنید در نهایت یک عدد ثابت میمونه ولی اون چیزی ک مرتبه رو تعیین میکنه lgn ینی همون ارتفاع درخت هست که این زمانی هست ک اجرای الگوریتم طول میکشه لزوما اون مقدار جلوی f مرتبه رو تعیین نمیکنه باید تعداد تکرار الگوریتم رو هم درنظر گرفت پس مرتبه ی زمانی تتای lgn میشه.
۰
ارسال: #۶
  
RE: مرتبه زمانی این تابع چی میشه ؟
سوال یه کم مشکل داره. بهترین حالت جواب یک هست. این سوال رو از کجا اوردین؟ از خودتون در اوردین یا جایی دیدین؟
ارسال: #۷
  
RE: مرتبه زمانی این تابع چی میشه ؟
-۱
ارسال: #۸
  
RE: مرتبه زمانی این تابع چی میشه ؟
به نظر من از مرتبه [tex]\frac{1}{n}[/tex]میشه. چرا که رابطه ی غیربازگشتی این تابع میشود: [tex]f(n)=2-\frac{2}{n}[/tex]
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close