چرا [tex]\frac{n^2}{\log n}[/tex] نه عضو امگا نه عضو اُ و نه عضو تتای [tex]n^2[/tex] نیست
پس چطوری می تونیم مرتبه ی زمانی الگوریتم زیرو بدست بیاریم وقتی نمی تونیم از قضیه اصلی استفاده کنیم؟
[tex]T(n)=9T(\frac{n}{3}) \frac{n^2}{\log n}[/tex]
پاسخ:
در توضیح قسمت اول سوالتوون:
چون:
[tex]\lim_{n\: \longrightarrow\infty}\: \frac{\frac{n^2}{\log\: n}}{n^2}=\lim_{n\: \longrightarrow\: \infty}\: \frac{1}{\log\: n}=0[/tex]
پس [tex]\frac{n^2}{\log\: n}\: \notin\: \theta(n^2)\: \: \: \: \: but\: \: \: \: \frac{n^2}{\log\: n}\in\: O(n^2)[/tex]
[tex]and\: \: \: \: \frac{n^2}{\log\: n}\in\: o(n^2)[/tex]
سوال در پیوست
برای توضیح راحتتر این قضیه بعضی از کتب مرجع از این روش برای شروط الگوریتم استفاده میکنن که فک کنم برای درک راحتتر باشه. من سه صفحه مربوط به اوون رو پیوست کردم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
در توضیح مثال شما:
[tex]T(n)=9\cdot T(\frac{n}{3}) \frac{n^2}{\log\: n}\: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: f(n)=\frac{n^2}{\log\: n}\: \: \: \: \: \: \: \: \: \: \: \: \: a=9\: \: \: \: \: \: \: \: \: \: \: b=3\: \: \: ,\: \: \: \: \: \: f(n)=O(n^2)[/tex]
اما برای استفاده از شرط اول باید [tex]\: f(n)=\theta(n^c)\: \: \: \: \: \: \: \: \: \: ,\: \: \: \: c>\log_b^a\: \: \: \: \: or\: \: \: \: \: \: c>\log^9_3=2[/tex]
اما همانطور که میدانیم [tex]\frac{n^2}{\log\: n}=O(n^2)[/tex] پس هم مرتبه نیستند و مجاز نیستیم از شرط اول استفاده کنیم.
من ریاضیاتم خیلی خوب نیست، ولی به نظرم:
بحث سر کوچکتر و بزرگتر نیست، بلکه باید تفاوتی در حد چند جمله‌ای یا بزرگتر داشته باشند؛
تفاوت در حد پلی لگاریتمی در Nهای بزرگ ناچیز است و تحت تأثیر عبارات کم اهمیتی قرار می‌گیرد که در مفهوم تتا نادیده گرفته شده‌اند.
درسته باید تفاوت درجه توان اوون دو تا یه چیزی مثل [tex]n^{\epsilon}\: \: \: or\: \: n^{\varepsilon}[/tex] باشه.اینم میدونیم که [tex]n^a>(\log\: n)^b[/tex]