سوال الگوریتم - تتا

[kale_sabz]

سلام بچه ها خوبید 1 تمرین امگا و ا بیگ رو حل کردم نمیدونم درسته یا نه آخه سر کلاس نبودم اصلا" از رو جزوه یه نگاه انداختم حل کردم نمیدونم دیگه ... در ضمن تتا رو یاد نگرفتم چطوریه میشه تتا رو برام توضیح بدین ؟ و بگین اینا درستن یا نه مرسی یا درستشو بگید چیزی کمو کسر نداره ؟

[kale_sabz]

سلام
کسی از بروبچ نیست جواب ما رو بده ؟

[kale_sabz]

اگه داش مجتبی پی سی بود حل بوداااااااااااا

[SJJ]

خیلی ساده،
Big O ی هر تابع، هر مرتبه با درجه ای بزرگتر یا مساوی با درجه ی تابع می تونه باشه، یعنی کران بالا.
امگای هر تابع، هر مرتبه با درجه ای کمتر یا مساوی با درجه ی تابع می تونه باشه، یعنی کران پایین.
و تتای هر تابع، باید هم مرتبه بادرجه ی تابع باشه.

پس:

کد: انتخاب همه

n!+7n^5=O(n!)

اون یکی جواب هاتون درسته.
اگه لازمه بگین تا تعریف دقیق ریاضی شو بگم.

[kale_sabz]

دوست عزیز از محبتت ممنونم

میشه ریاضی اش هم بگید ممنون میشم
و لطفا برای تتا یه مثال هم بزنید
سپاسگزارم

[kale_sabz]

ممننون میشم دوست عزیز

و یه سوال میشه بگید در یه ماتریس 64*64 چند عمل ضرب و جمع انجام میشه ؟ (استراسن )

[SJJ]

دوست عزیز از محبتت ممنونم

میشه ریاضی اش هم بگید ممنون میشم
و لطفا برای تتا یه مثال هم بزنید
سپاسگزارم

برای یک تابع پیچیدگی مفروض ƒ(n)

کد: انتخاب همه

 ،O (ƒ (n)

”اُوی بزرگ“ مجموعه ای از توابع پیچیدگی g (n) است که برای آن ها یک ثابت حقیقی مثبت c و یک عدد صحیح غیر منفی N وجود دارد به قسمی که به ازای همه ی N =< n داریم:

کد: انتخاب همه

g (n) >= c × ƒ (n)

برای یک تابع پیچیدگی مفروض ƒ(n)

کد: انتخاب همه

 Ω (ƒ(n)

مجموعه ای از توابع پیچیدگی g (n) است که برای آن ها یک عدد ثابت حقیقی مثبت c و یک عدد صحیح غیر منفی N وجود دارد به قسمی که به ازای همه ی N =< n داریم:

کد: انتخاب همه

g (n) =<  c × ƒ (n)

برای یک تابع پیچیدگی مفروض ƒ(n)، داریم:

کد: انتخاب همه

θ (ƒ(n)) = O (ƒ(n)) ∩ Ω (ƒ(n))

یعنی θ(ƒ(n)) مجموعه ای از توابع پیچیدگی g (n) است که برای آن ها ثابت های حقیقی مثبت c وd و عدد صحیح غیر منفی N وجود دارد به قسمی که :

کد: انتخاب همه

c × ƒ (n) <= d × ƒ(n)

-------------------------------------------------------------------------------
الگوریتم ها یی با پیچیدگی زمانی ازقبیل n و100n را الگوریتم های زمانی خطی می گویند.مثل:

کد: انتخاب همه

θ(n) 

مجموعه کامل توابع پیچیدگی را که با توابع درجه دوم محض قابل دسته بندی باشند، (n²)θ می گویند. مثل :
197n²+6logn+7n
(n²/2)+7000n

منبع:طراحی الگوریتم ها، نیپولیتان، نعیمی پور

اطلاعات بیشتر در این فایل Word
http://www.tehran-markaz.com/Akbarian/F ... rithms.doc

[cheraghe_jado]

سلام بچه ها خوبید
بچه ها منظورشون از اینکه میگن صحت عبارت زیر رو بررسی کنید چیه ؟ یعنی چی بنویسیم ؟ یعنی همونجوری که kale_sabz گفت باید به ازای c , n مقدار بدیم ؟ میشه اینو حل کنین ممنون میشم تا حساب کار دستم بیاد عکسشو با یه تابع بازگشتی میزارم ممنون میشم حالیم کنین من تو برگم چی چی باس بنویسم ؟سومین مثال تابع بازگشتی میشه حلش کنین واسم ؟
و دو سوال 4 جوابی هم دارم
1. کدوم الگوریتم برنامه نویسی پویا نیست
دوره گرد - دودویی بهینه -هافمن - کوله پشتی صفرو یک
2.کدام روش برای حل مسئله جستجو دودویی بهینه است ؟
عقبگرد - تقسم و حل -پویا- حریصانه
ممنون از محبتتون .
اینم عکس :

[cheraghe_jado]

کسی نیست جواب بده چه بد

[cheraghe_jado]

ای بابا فوریه کسی نیست جواب بده چه بد

[cheraghe_jado]

چرا اینجا عین کویر سوتو کوره ؟

[cheraghe_jado]

آقا جون مادرتون بیاین جواب منو بدید حیاتیه