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