در معادله زیر
[tex]T(n)=4T(\frac{\sqrt{n}}{3}) log^{2}n[/tex]
برای از بین بردن رادیکال باید [tex]n=2^{m}[/tex]m} قرار بدیم
چرا اینجوری می کنیم؟ و بعدش در کتاب وقتی اینکار رو کرده نوشته [tex]T(2^{m})=4T(2^{\frac{m}{2}}) m^{2}[/tex]
پس کسر ۳ کجا رفته؟؟؟
سلام دوست مانشتی:
د راینجا چون nما رادیکالی است باید به nتبدیل بشه بخاطر همین با تغییر متغیر این کار کرده وn=2^mفرض کرده که میشه[tex]\sqrt{2^m}=2^m/2[/tex]
که با این روش nرو از زیر رادیکال بیرون و به nاز درجه ۱تبدیل میکنه باز هم برای ساده شدن تغییرمتغیر میده [tex]s(m)=T(2^m)[/tex]
[tex]s(m)=T(2^m)[/tex]که الان رابطه به شکل[tex]s(m)=4s(m/2) m^2[/tex]
تبذیل میشه که از طریق رابطه اصلی قابل حل وهم اینکهn=2^mهم برابرm=logn میباشد.
از۳صرفنطرکرده.
دوستان دیگه هم نطربدن و اگه اشکالی داره اصلاح کنن.
خب من اصلا سوالم اینه که چرا n=2^m
(۲۰ مهر ۱۳۹۰ ۰۱:۳۳ ب.ظ)پشتکار نوشته شده توسط: خب من اصلا سوالم اینه که چرا n=2^m
هم برای ساده سازی بیشتر nیاهمان عدد زیر رادیکال را توانی از ۲فرض کرده.این که خیلی واضحه برای اینکه قراره باتغییر متغیر حل بشه و ساده سازی لازم رو انجام بده.
بری اینکه nرو از زیر رادیکال بیرون بیاره فرض میکنه که nتوانی از ۲باشه(بخاطر همین گفتهn=2^m و) ساده سازی روانجام میده.
بقیه دوستان هم کمک دوستمون کنند من فقط همینقدر میدونم.
چیزی که خودم بهش رسیدم رو می نویسم و خواهش می کنم دوستان عیبها و درست یا غلط بودنشو بهم بگن:
داریم:
[tex]T(n)= 4T(\frac{\sqrt{n}}{3}) log^{2}n[/tex]
حال برای از بین بردن لگاریتم [tex]n=2^{m}[/tex] را بجای n قرار می دهیم.
پس داریم:
[tex] T(2^{m})=4T(\frac{2^{\frac{m}{2}}}{3}) m^{2} [/tex]
حال از داخل [tex] T() [/tex] لگاریتم می گیریم و داریم:
[tex]S(m)=4S(log{{\frac{2^{\frac{m}{2}}}{3}}}) m[/tex]
که با ساده سازی داریم:
[tex] \frac{m}{2}-log_{2}^{3}=\frac{m}{2}-(1 \varepsilon )[/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] گرفتم.