وقتی توان log منفی هستش فک کنم فقط از طریق درخت بازگشتی حل بشه!

(۰۴ بهمن ۱۳۹۱ ۰۵:۲۲ ب.ظ)zfmo نوشته شده توسط:  سلام
ببخشید می شه مرتبه های زمانی مثال های زیر را برایم توضیح دهید ( با نماد های مجانبی)
$T(n)=5T(n/5) {\frac{n}{logn}}$

T(n)=T(n/2)+T(n/8)+T(n/4)+n

T(n)=T(n-1)+1/n
T(n)=T(n-1)+log n
T(n)=n^1/2 T (n^1/2) + n

ما قضیه اصلی را خوندیم که به شکل aT(n/b) +f(n) a بود یا آنهایی که به شکل aT(n-b) +c
اینها را چه جوری حل کنیم؟
من خیلی توی اینا مشکل دارم

سلام [/align]
برای اولی تغییر متغییر بده به ۵ به توان k و حلش کن فکر کنم بشه n * log(logn)
دومی رو : تغییر متغییر بده به ۲ به توان k و حل کن
سومی : بازش کن می شه جمع ۱ تا ۱/n که می شه logn
چهارمی : بازش کن می شه جمع log 1 تا log (n) که میشه لگاریتم n فاکتوریل و تقریبا nlogn
پنجمی : تغییر متغییر به ۲ به توان k

quote='ana_12345' pid='155851' dateline='1358958069']
برای اولی تغییر متغییر بده به ۵ به توان k و حلش کن فکر کنم بشه n * log(logn)
[/quote]
من با این تغییر متغیر شما نتونستم حلش کنم اگه میشه بیشتر توضیح بدید.
ولی با جوابتون موافقم!

(۱۳ بهمن ۱۳۹۱ ۰۵:۲۶ ب.ظ)csharpisatechnology نوشته شده توسط:  $5^2T(n/5^2) 5(\frac{n}{5*lg(\frac{n}{5})}) \frac{n}{lgn}\sim eq h*o(n)=o​(nlgn)$

به نظرم این حل درست نیست!

(۰۴ بهمن ۱۳۹۱ ۰۸:۵۱ ب.ظ)ana_12345 نوشته شده توسط:  

(04 بهمن ۱۳۹۱ ۰۵:۲۲ ب.ظ)zfmo نوشته شده توسط:  سلام
ببخشید می شه مرتبه های زمانی مثال های زیر را برایم توضیح دهید ( با نماد های مجانبی)
$T(n)=5T(n/5) {\frac{n}{logn}}$

T(n)=T(n/2)+T(n/8)+T(n/4)+n

T(n)=T(n-1)+1/n
T(n)=T(n-1)+log n
T(n)=n^1/2 T (n^1/2) + n

ما قضیه اصلی را خوندیم که به شکل aT(n/b) +f(n) a بود یا آنهایی که به شکل aT(n-b) +c
اینها را چه جوری حل کنیم؟
من خیلی توی اینا مشکل دارم

سلام [/align]
برای اولی تغییر متغییر بده به ۵ به توان k و حلش کن فکر کنم بشه n * log(logn)
دومی رو : تغییر متغییر بده به ۲ به توان k و حل کن
سومی : بازش کن می شه جمع ۱ تا ۱/n که می شه logn
چهارمی : بازش کن می شه جمع log 1 تا log (n) که میشه لگاریتم n فاکتوریل و تقریبا nlogn
پنجمی : تغییر متغییر به ۲ به توان k

سلام، من تلاش کردم T(n)=T(n/2)+T(n/8)+T(n/4)+n رو با تغییر متغیر حل کنم ولی موفق نشدم. بعد از تغییر متغیر رابطه تبدیل به شکل زیر میشه:
$n=2^k$
$T(2^k) = T(2^{k-1}) T(2^{k-2}) T(2^{k-3}) 2^k$
$F(k) = T(2^k) => F(k) = F(k-1) F(k-2) F(k-3) 2^k$
در اصل من توی حل کردن این رابطه‌ی آخری مشکل داشتم. سعی کردم با تکرار حلش کنم که به جای خوبی نرسیدم. ممنون می‌شم کمک کنید.

سمت چپ میشه teta_n
اما سمت راست میشه nlg^{-1}n
چون توان از ۰ کمتر شد با master نمیشه حلش کرد.

فکر کنم با درخت تصمیم میشه این:
$5^2T(n/5^2) 5(\frac{n}{5*lg(\frac{n}{5})}) \frac{n}{lgn}\sim eq h*o(n)=o(nlgn)$
رابطه ی فوق به اندازه ی o(n) رشد می کنه و ارتفاع درخت میشه lgn
شایدم به توان لگاریم یکی باید اضاف بشه یا کلا جواب همون ارتفاع درخت یا lgn میشه شک دارم

سلام

اثباتش تو پیوست هست امیدوارم کامل باشه

موفق باشید .

(۱۷ بهمن ۱۳۹۱ ۰۳:۵۶ ب.ظ)elahehab نوشته شده توسط:  سلام، من تلاش کردم T(n)=T(n/2)+T(n/8)+T(n/4)+n رو با تغییر متغیر حل کنم ولی موفق نشدم.

با استفاده از درخت بازگشت میشه خیلی خیلی راحت حلش کرد. حلش تو کتاب CLRS اومده