تالار گفتمان مانشت

سلام دوستان
میشه بگید مرتبه زمانی این تابع چی میشه ؟

[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 باشه آیا صورت این عبارت زمانی درسته؟
آخه من ندیدم که تایم معادله بازگشتی روبه صورت نصف تایم قبلی تعریف کنیم. چون در این صورت تابع ما دیگه بازگشتی نداره.
دقیق تر اینکه ضریب تابع زمان بازگشتی باید 1 یا عدد صحیح بزرگتر 1 باشه تا بتونیم بگیم که تابع ما چند بار در هر مرحله بازگشت خورده !!!

پ.ن : اگر که این سوال صورت دقیق همون تابع F باشه و بخوایم تابع T اون رو استخراج و سپس حل کنیم براحتی مشخصه که Logn میشه

سلام.شما وقتی این رابطه رو تا آخر باز کنید در نهایت یک عدد ثابت میمونه ولی اون چیزی ک مرتبه رو تعیین میکنه lgn ینی همون ارتفاع درخت هست که این زمانی هست ک اجرای الگوریتم طول میکشه لزوما اون مقدار جلوی f مرتبه رو تعیین نمیکنه باید تعداد تکرار الگوریتم رو هم درنظر گرفت پس مرتبه ی زمانی تتای lgn میشه.

(20 مرداد 1393 06:22 ب.ظ)ADELZX نوشته شده توسط: [ -> ]بنظر شما دوستان اگه این عبارت معرف تابع T باشه آیا صورت این عبارت زمانی درسته؟
آخه من ندیدم که تایم معادله بازگشتی روبه صورت نصف تایم قبلی تعریف کنیم. چون در این صورت تابع ما دیگه بازگشتی نداره.
دقیق تر اینکه ضریب تابع زمان بازگشتی باید ۱ یا عدد صحیح بزرگتر ۱ باشه تا بتونیم بگیم که تابع ما چند بار در هر مرحله بازگشت خورده !!!

پ.ن : اگر که این سوال صورت دقیق همون تابع F باشه و بخوایم تابع T اون رو استخراج و سپس حل کنیم براحتی مشخصه که Logn میشه

باهاتون موافقم 1/2 بار بازگشت کردن معنی نداره!

سوال یه کم مشکل داره. بهترین حالت جواب یک هست. این سوال رو از کجا اوردین؟ از خودتون در اوردین یا جایی دیدین؟

(21 مرداد 1393 12:37 ب.ظ)901845 نوشته شده توسط: [ -> ]سوال یه کم مشکل داره. بهترین حالت جواب یک هست. این سوال رو از کجا اوردین؟ از خودتون در اوردین یا جایی دیدین؟

نه جایی ندیدم ، برام سوال پیش اومد که اگه تنها تصاعد هندسی کاهنده باشه ، مرتبه زمانیش چی میشه گفتم اینجا از دوستات بپرسم