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

[hercool]

سلام خدمت دوستان
می خوام بدونم این مسئله چطور حل شده من یکم مشکل دارم تو حلش که در ادامه متذکر اون قسمت از جواب سوال میشم

http://www.img4up.com/up2/81583135210106.gif

خوب اینجا باید نماد تتا رو در t(n) بدست بیاریم
حالا اومده و گفته نشان می دهیم که این معادله برقرار است

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

خوب اینجا باید نماد تتا رو در t(n) بدست بیاریم
حالا اومده و گفته نشان می دهیم که این معادله برقرار است

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 از کجا میاد.