زمان کنونی: ۰۸ آذر ۱۳۹۹, ۰۹:۳۹ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

مرتبه الگوریتم ها

ارسال:
  

hattrick پرسیده:

مرتبه الگوریتم ها

سلام دوستان، لطفا به من تو اثبات این تساوی کمک کنید Sadطراحی الگوریتم- پوران- مرتبه الگوریتم- ص ۱۲)
۲[tex]2^{\sqrt{2logn}}=n^{\sqrt{\frac{2}{logn}}}[/tex]
و اینکه به نظرتون تساوی زیر درسته؟
[tex]f(n) O(f(n))\epsilon \theta (f(n))[/tex]
[/align]

۰
ارسال:
  

- rasool - پاسخ داده:

مرتبه الگوریتم ها

شما علامت O رو به معنای کوچکترمساوی (از لحاظ رشد) و علامت تتا رو دقیقا مساوی (از لحاظ رشد) بگیرید.

سوال اول شما:
بله می تونه باشه. [tex]\large n=O(n^{2})[/tex]

سوال دوم شما:
مثالی رو می زنم:
فرض کنید [tex]\large f(n)=n^{2} , g(n)=n[/tex]
حالا داریم:
[tex]\large f(n) g(n)=n^{2} n = f(n) O(f(n))[/tex]

در این عبارت‌، تابع f با تابعی جمع شده که مرتبه آن کوچکتر یا مساوی مرتبه f می باشد. در نتیجه بدیهی است که حاصل این جمع‌، تابعی خواهد بود که مرتبه اش مساوی مرتبه f است. یعنی:

[tex]\large f(n) g(n)=n^{2} n = f(n) O(f(n))=\theta (f(n))=\theta (n^{2})[/tex]

خوب حالا شما می تونید در سمت راست عبارت به جای [tex]\large n^{2}[/tex]
توابعی با رشد بالاتر رو هم قرار بدید(البته با استفاده از علامت O به جای تتا ). مثلا

[tex]\large n^{2} n=\theta (n^{2}), n^{2} n=O(n^{2}), n^{2} n=O(n^{3}),n^{2} n=O(n^{4}), ...[/tex]

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

توجه کنید که اگر مثلا تابع a برابر بیگ اوی تابع bباشه آنگاه لزوما برابر تتای آن نخواهد بود.

اما اگر مثلا تابع a برابر تتای تابع b باشه آنگاه برابر بیگ اوی b و نیز برابر بیگ اوی تمام توابعی که رشدشان بیشتر از b است‌، نیز خواهد بود.

۰
ارسال:
  

- rasool - پاسخ داده:

الله

نظر من در مورد سوال دوم:

این تساوی درسته. فرض کنید تابع f از یک مرتبه ای هست. در عبارت سمت چپ‌، تابع f با تابعی جمع شده که مرتبه آن کوچکتر یا مساوی مرتبه f می باشد. در نتیجه بدیهی است که حاصل این جمع‌، تابعی خواهد بود که مرتبه اش مساوی مرتبه f است.
نکته ۱‌: بیگ اوی f یعنی هر تابع دلخواهی که مرتبه اش کوچکتر یا مساوی مرتبه f است.
نکته ۲‌: تتای f یعنی هر تابع دلخواهی که مرتبه اش مساوی مرتبه f است.

و سوال اول:
در فایل word نوشتم‌:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

۰
ارسال:
  

summer_66 پاسخ داده:

RE: مرتبه الگوریتم ها

(۰۷ مهر ۱۳۹۰ ۱۲:۵۰ ب.ظ)hattrick نوشته شده توسط:  سلام دوستان، لطفا به من تو اثبات این تساوی کمک کنید Sadطراحی الگوریتم- پوران- مرتبه الگوریتم- ص ۱۲)
[tex]2^{\sqrt{2logn}}=n^{\sqrt{\frac{2}{logn}}}[/tex]
و اینکه به نظرتون تساوی زیر درسته؟
[tex]f(n) O(f(n))\epsilon \theta (f(n))[/tex]

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

۰
ارسال:
  

رضا_ایرانی پاسخ داده:

RE: مرتبه الگوریتم ها

(۰۷ مهر ۱۳۹۰ ۱۲:۵۰ ب.ظ)hattrick نوشته شده توسط:  سلام دوستان، لطفا به من تو اثبات این تساوی کمک کنید Sadطراحی الگوریتم- پوران- مرتبه الگوریتم- ص ۱۲)
۲[tex]2^{\sqrt{2logn}}=n^{\sqrt{\frac{2}{logn}}}[/tex]
و اینکه به نظرتون تساوی زیر درسته؟
[tex]f(n) O(f(n))\epsilon \theta (f(n))[/tex]
[/align]

برای اولی از طرفین لگاریتم با پایه دو بگیرید بعد به توان برسونید.

[tex]\log (2^{\sqrt{2\log n}})=\log (n^{\sqrt{\frac{2}{\log n}}})\Rightarrow \sqrt{2\log n}=\log n*\sqrt{\frac{2}{\log n}}\Rightarrow 2\log n=\(log n) ^{2} * \frac{2}{\log n} \Rightarrow 2\log n=2\log n[/tex]


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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مرتبه ایجاد درخت rad.bahar ۱ ۱۴۵ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۱۵۱ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۸,۶۸۹ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  مرتبه زمانی Sanazzz ۱۷ ۵,۹۳۰ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۱,۱۵۲ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  مرتبه مانی Sanazzz ۳ ۱,۱۴۵ ۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ
آخرین ارسال: Sanazzz
  مرتبه زمانی Sanazzz ۰ ۶۳۸ ۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ
آخرین ارسال: Sanazzz
  مشکل در محاسبه مرتبه ایک سوال Mr.R3ZA ۰ ۷۵۳ ۲۴ خرداد ۱۳۹۷ ۰۱:۰۳ ب.ظ
آخرین ارسال: Mr.R3ZA
  سوال ۱۱۵- مهندسی ۹۶- منطق مرتبه اول mzi ۰ ۵۹۵ ۲۱ فروردین ۱۳۹۷ ۰۵:۰۵ ب.ظ
آخرین ارسال: mzi
  جمله مرتبه اول ss311 ۰ ۵۴۴ ۲۶ بهمن ۱۳۹۶ ۰۸:۱۶ ب.ظ
آخرین ارسال: ss311

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close