سلام دوستان، لطفا به من تو اثبات این تساوی کمک کنید
طراحی الگوریتم- پوران- مرتبه الگوریتم- ص ۱۲)۲[tex]2^{\sqrt{2logn}}=n^{\sqrt{\frac{2}{logn}}}[/tex]
و اینکه به نظرتون تساوی زیر درسته؟
[tex]f(n) O(f(n))\epsilon \theta (f(n))[/tex]
[/align]
نظر من در مورد سوال دوم:
این تساوی درسته. فرض کنید تابع f از یک مرتبه ای هست. در عبارت سمت چپ، تابع f با تابعی جمع شده که مرتبه آن کوچکتر یا مساوی مرتبه f می باشد. در نتیجه بدیهی است که حاصل این جمع، تابعی خواهد بود که مرتبه اش مساوی مرتبه f است.
نکته ۱: بیگ اوی f یعنی هر تابع دلخواهی که مرتبه اش کوچکتر یا مساوی مرتبه f است.
نکته ۲: تتای f یعنی هر تابع دلخواهی که مرتبه اش مساوی مرتبه f است.
و سوال اول:
در فایل word نوشتم:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۰۷ مهر ۱۳۹۰ ۱۲:۵۰ ب.ظ)hattrick نوشته شده توسط: سلام دوستان، لطفا به من تو اثبات این تساوی کمک کنید
[tex]2^{\sqrt{2logn}}=n^{\sqrt{\frac{2}{logn}}}[/tex]
و اینکه به نظرتون تساوی زیر درسته؟
[tex]f(n) O(f(n))\epsilon \theta (f(n))[/tex]
در مورد سوال اولتون البته با اجازه نقل قول شما رو اصلاح کردم چون یه ۲ اضافه نوشتید که نمیدونم چی بوده.
[attachment=1267]
(۰۷ مهر ۱۳۹۰ ۱۲:۵۰ ب.ظ)hattrick نوشته شده توسط: سلام دوستان، لطفا به من تو اثبات این تساوی کمک کنید
۲[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 میاد که تساوی درست میشه.
نقل قول: رضا جان اینگونه سوالها را نباید به این شکل حل کنی به این دلیل که در موقع کنکور دو طرف داده نمی شود که بخواهیم لگاریتم بگیرم و اثبات کنیم. و اگر بخواهی حفظ کنی هم امکان فراموش شدن فرمولها به دلیل زیاد بودنشان نیز هست.
بله درست میفرمایید، اما اگر توجه کنید دوستمون اثبات درستی تساوی رو خواسته بودن که اینجور حل کردم وگرنه به نظر من اصلا نیازی به حل هم نیست و با عدد گذاری ساده صحت تساوی اثبات میشه. اما حرفتون هم کاملا درسته.
(۱۵ مهر ۱۳۹۰ ۰۵:۲۴ ق.ظ)mmasoud نوشته شده توسط: مرتبه عبارت n به توان ۱/log n چیه؟ببخشید،فرمول نویسی بلد نیستم.
کافیه که به جای اون عدد ۱ در صورت Log 2 بگذارید:
[tex]\large n^{\frac{1}{log n}}=n^{\frac{log 2}{logn}}=\sqrt[logn]{n^{log 2}}=\sqrt[logn]{2^{logn}}=2^{\frac{logn}{logn}}=2=O(1)[/tex]
(۱۶ مهر ۱۳۹۰ ۱۱:۳۴ ب.ظ)mam نوشته شده توسط: دوستان ببخشید من یک سؤال برام پیش اومده درباره همین بخش دوم این سؤال:
یکی از دلایل اینکه نماد تتا مطرح شده٬ نقص Big-O در تعدد عبارات بوده. برای مثال[tex]f(n)=3n \to f(n) \epsilon O(n)[/tex] اما در عین حال می‌تونه [tex]f(n)=n \to f(n) \epsilon O(n^{2})[/tex] هم می‌تونه باشه. بنابراین در موارد خاص رابطه‌ی دوم نمی‌تونه نادرست باشه؟
طبق توضیحی که در پست دوم دادم، این رابطه درسته.
سوال شما رو دقیقا متوجه نشدم. کدوم موارد خاص؟
شما علامت 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 است، نیز خواهد بود.