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

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

ارسال:
  

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 میاد که تساوی درست میشه.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۳,۸۳۸ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۰۴۰ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۱۹۸ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  مرتبه زمانی Sanazzz ۱۷ ۱۹,۱۲۴ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۳,۴۰۷ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  افزایش واگرایی الگوریتم های مبتنی بر جمعیت moslem73421 ۲ ۲,۷۷۱ ۰۵ شهریور ۱۳۹۸ ۱۰:۵۳ ب.ظ
آخرین ارسال: cpt.mazi
  دانلود آموزش تصویری کلاس درس تحلیل و طراحی الگوریتم های پیشرفته دانشگاه فردوسی jazana ۱۳ ۱۲,۷۴۷ ۱۰ خرداد ۱۳۹۸ ۰۵:۴۲ ب.ظ
آخرین ارسال: Valipourh20
  مرتبه مانی Sanazzz ۳ ۳,۲۸۴ ۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ
آخرین ارسال: Sanazzz
Question تفاوت تعداد مقایسه های مورد نیاز در الگوریتم های متفاوت porseshgar ۰ ۱,۹۲۳ ۱۵ بهمن ۱۳۹۷ ۱۲:۳۳ ب.ظ
آخرین ارسال: porseshgar

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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