محاسبه تتا در این معادله

[hercool]

سلام خدمت دوستان
می خوام بدونم این مسئله چطور حل شده من یکم مشکل دارم تو حلش که در ادامه متذکر اون قسمت از جواب سوال میشم
http://www.img4up.com/up2/81583135210106.gif

http://www.img4up.com/up2/81583135210106.gif
خوب اینجا باید نماد تتا رو در t(n) بدست بیاریم
حالا اومده و گفته نشان می دهیم که این معادله برقرار است
http://www.img4up.com/up2/1182488415985315.gif

http://www.img4up.com/up2/1182488415985315.gif
حالا چرا n به توان دو ؟
دوم اومده حساب کرده و گفته که c اندیس 2 بزگتر مساوی 1/2 هست به ازای n بزرگتر مساوی 1 چطور؟
و سوم گفته که c اندیس 1 کوچکتر مساوی 1/4 به ازای n کوچکتر مساوی 7 برقرار است چطور؟
مخصوصا 1/4 چطور بدست اومده ؟
ممنون

[مسعود اقدسی فام]

سلام خدمت دوستان
می خوام بدونم این مسئله چطور حل شده من یکم مشکل دارم تو حلش که در ادامه متذکر اون قسمت از جواب سوال میشم
http://www.img4up.com/up2/81583135210106.gif

http://www.img4up.com/up2/81583135210106.gifخوب اینجا باید نماد تتا رو در t(n) بدست بیاریم
حالا اومده و گفته نشان می دهیم که این معادله برقرار است
http://www.img4up.com/up2/1182488415985315.gif

http://www.img4up.com/up2/1182488415985315.gifحالا چرا n به توان دو ؟
دوم اومده حساب کرده و گفته که c اندیس 2 بزگتر مساوی 1/2 هست به ازای n بزرگتر مساوی 1 چطور؟
و سوم گفته که c اندیس 1 کوچکتر مساوی 1/4 به ازای n کوچکتر مساوی 7 برقرار است چطور؟
مخصوصا 1/4 چطور بدست اومده ؟
ممنون

راستش من کامل متوجه سوالها نشدم. ولی اینکه (T(n با تعریف بالا عضو تتای n به توان دو هست کجاش ابهام داره؟

[hercool]

می خوام بدونم ایا میشه بجای توان دو بزاری 3
و سوال اصلیم مربوط به عدد ثابت هاست که گفته میشه 1/4 این رو از کجا اورده

[mohsensaghafi]

سلام دوست عزیز.
اوردر برنامه همیشه تابعی از بزرگترین توان اون هست. یعنی شما که تو این مسئله توان دوم داری تتا هم از توان دوم n خواهد شد. اگر توان 3 بود باید توان سوم n رو به تتا نسبت می دادیم. چون در پیچیدگی زمانی فقط این توانها هستند که نقش بازی می کنند نه اعداد ثابت. چون بررسی پیچیدگی ها در زمانی بررسی می شوند که n به سمت بینهایت میل کند. برای همین اعداد ثابت اثر خود را از دست می دهند.
موفق باشید و پیروز

[hercool]

یعنی چون در تابع ما t(n) بالاترین توابعش 2 هست تتا ما هم توان دو داره این برداشت من درسته؟
بعد ممنون میمش بگید 1/4 چجوری بدست اومده ؟

[mohsensaghafi]

سلام دوست عزیز.
برای بدست آوردن تتا باید یک تابع g(n) تعریف کنیم به همراه c1 و c2 و n0 پیدا کنیم بطوری که به ازای n های بزرگتر از n0 فرمول زیر برقرار باشد.


c1 g(n) <= f(n) <= c2 g(n)

در اینجا تابع g(n)= n^2 است و مقادیر c2=1/2. چون تابع f(n) یک 3n- دارد پس همواره کوچکتر از c2 g(n) می شود. حال برای پیدا کردن c1 آنرا برابر 1/4 گرفته است. این عدد می توانست عدد دیگری باشد. فقط باید در شرایط مسئله صدق کند. در اینجا 1/4 گرفته که بعد از 7 همواره در شرایط مسئله صدق می کند.

توجه: مقادیر c1 , c2 , تابع g مقادیری متغییر هستند و ممکن است برای یک مسئله مقادیر متنوعی برای این متغییر ها پیدا کنید.
موفق و پیروز

[hercool]

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

[mohsensaghafi]

سلام دوست عزیز.
شما به ازای n های بزرگتر از 12 که حساب کنی با توجه به C1 , C2 که قبلا گفتم، تمام عبارات درست خواهد بود.
موفق باشید و پیروز

[سعیدسعید]

سلام
البته این مسائل با استفاده از یکسری معادلات ریاضی حل می شوند که به نظر من اگر به کتاب طراحی الکوریتم نعیمی پور، به پیوست یک و دو نگاه کنید شاید جواب رو پیدا کنید که 1/4 از کجا میاد.