هوالعلیم
یک سوال ترکیبی و حدودا متوسط (تست کنکور ۸۸)
[tex]T(n)= 4T(\frac{\sqrt{n}}{3}) Log^{2}n[/tex]
این سوال با من.
فکر می کنم اینطوری حل می شه:
ابتدا تغییر متغیر [tex]n=3^{m}\Leftrightarrow m=Log _{3}^{n}[/tex] رو انجام می دیم. داریم:
[tex]T(n)= 4T(\frac{\sqrt{n}}{3}) Log^{2}n=T(3^{m})=4T(3^{\frac{m}{2}-1}) m^{2}\Rightarrow S(m)=4S(\frac{m}{2}-1) m^{2}\approx S(m)=4S(\frac{m}{2}) m^{2}[/tex]
که حالا با استفاده از قضیه اصلی می رسیم به: [tex]O(m^{2}Logm)[/tex]
و در نهایت با جایگزینی داریم:
[tex]O(Log^{2}n Log logn)[/tex]
پ ن: البته من برای راحتی کار و نیز چون بحث مرتبه هستش، گاها در حل سوال [tex]Log _{3}^{n}\approx Log _{2}^{n}[/tex] گرفتم.
ببخشید یک سؤال:
من تا اینجا رو پیش رفتم٬ اما بعدش شک کردم که از قضیه‌ی مستر میشه حل کرد یا نه.
یعنی اگر گاهی داشته باشیم: [tex]\small \dpi{80} S(\frac{m}{2}-1)[/tex] میتونیم برای مرتبه‌ی زمانی [tex]\small \dpi{80} S(\frac{m}{2})[/tex] در نظر بگیریم؟
چون به هر حال٬ توی رابطه‌ی اول٬ داره در هر بازگشت٬ یکی هم کم میشه (علاوه بر اینکه تقسیم میشه)
به نظرم:
در اکثر مواقع میشه چنین کاری رو انجام داد.دلیل حذف اون مقدار مثلا دو هم این هست که ما قراره مرتبه به دست بیاریم و تو مرتبه ما با n های بزرگ سروکار داریم پس مقادیر ثابت تاثیر چندانی ندارن. و نیز نسبت به اون تقسیم بر دو کردن، این منهای یک قابل چشم پوشی خواهد بود.
در نتیجه اگه فرضا سوالی رو می خواستیم با قضیه اصلی یا درخت یا ... حل کنیم و این عدد رو داشت (چه بعلاوه و چه منها) می شه از اون صرفنظر کرد .
(البته منظورم وقتی هستش که مثل اینجا کسر داریم و گرنه در مورد غیر کسر بدیهیه که این عدد تاثیر داره)
--------------------------------------------------------------------------
به هر حال منتظر نظرات اساتید گرامی هستیم.
-----------------------------------------------------------------------------------
پ ن: جا داره در مورد این نکته از آقای mfxpert تشکر کنم.
(۱۱ بهمن ۱۳۹۰ ۱۲:۵۰ ق.ظ)yaali نوشته شده توسط: به نظرم:
در اکثر مواقع میشه چنین کاری رو انجام داد.دلیل حذف اون مقدار مثلا دو هم این هست که ما قراره مرتبه به دست بیاریم و تو مرتبه ما با n های بزرگ سروکار داریم پس مقادیر ثابت تاثیر چندانی ندارن. و نیز نسبت به اون تقسیم بر دو کردن، این منهای یک قابل چشم پوشی خواهد بود.
در نتیجه اگه فرضا سوالی رو می خواستیم با قضیه اصلی یا درخت یا ... حل کنیم و این عدد رو داشت (چه بعلاوه و چه منها) می شه از اون صرفنظر کرد .
(البته منظورم وقتی هستش که مثل اینجا کسر داریم و گرنه در مورد غیر کسر بدیهیه که این عدد تاثیر داره)
فکر کنم بشه اینطور استدلال کرد: چون می تونیم علامت براکت( سقف و کف )درون پراتنز رابطه مثلا (T(n) = 2(n/b رو برداریم و با توجه به اینکه تقسیم یک عدد ثابت بر عدد دیگه بالاخره بعد از تعداد متناهی مرتبه به عددی کچکتر از ۱ تبدیل میشه پس این عدد درون براکت حذف میشه، پس میتونیم بدون نگرانی این مقدار ثابت رو حذف کنیم.
پس ما مدام داریم اون عدد ثابت و n رو بر b تقسیم میکنیم ،در واقع n خیلی بزرگه و معلوم نیست در n/b کی به شرط مرزی برسیم اما یک عدد ثابت مثل a در طی تعداد متناهی وقتی بر b تقسیم میشه، میشه یه عدد کوچک و این عدد کوچک درون براکت برابر صفر هست .
