سلام
ببخشید می شه مرتبه های زمانی مثال های زیر را برایم توضیح دهید ( با نماد های مجانبی)
[tex]T(n)=5T(n/5) {\frac{n}{logn}}[/tex]
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
اینها را چه جوری حل کنیم؟
من خیلی توی اینا مشکل دارم
وقتی توان log منفی هستش فک کنم فقط از طریق درخت بازگشتی حل بشه!
(۰۴ بهمن ۱۳۹۱ ۰۵:۲۲ ب.ظ)zfmo نوشته شده توسط: سلام
ببخشید می شه مرتبه های زمانی مثال های زیر را برایم توضیح دهید ( با نماد های مجانبی)
[tex]T(n)=5T(n/5) {\frac{n}{logn}}[/tex]
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
سمت چپ میشه teta_n
اما سمت راست میشه nlg^{-1}n
چون توان از ۰ کمتر شد با master نمیشه حلش کرد.
فکر کنم با درخت تصمیم میشه این:
[tex]5^2T(n/5^2) 5(\frac{n}{5*lg(\frac{n}{5})}) \frac{n}{lgn}\sim eq h*o(n)=o(nlgn)[/tex]
رابطه ی فوق به اندازه ی o(n) رشد می کنه و ارتفاع درخت میشه lgn
شایدم به توان لگاریم یکی باید اضاف بشه یا کلا جواب همون ارتفاع درخت یا lgn میشه شک دارم
quote='ana_12345' pid='155851' dateline='1358958069']
برای اولی تغییر متغییر بده به ۵ به توان k و حلش کن فکر کنم بشه n * log(logn)
[/quote]
من با این تغییر متغیر شما نتونستم حلش کنم اگه میشه بیشتر توضیح بدید.
ولی با جوابتون موافقم!
(۱۳ بهمن ۱۳۹۱ ۰۵:۲۶ ب.ظ)csharpisatechnology نوشته شده توسط: [tex]5^2T(n/5^2) 5(\frac{n}{5*lg(\frac{n}{5})}) \frac{n}{lgn}\sim eq h*o(n)=o(nlgn)[/tex]به نظرم این حل درست نیست!
سلام
اثباتش تو پیوست هست امیدوارم کامل باشه
موفق باشید .
(۰۴ بهمن ۱۳۹۱ ۰۸:۵۱ ب.ظ)ana_12345 نوشته شده توسط:(04 بهمن ۱۳۹۱ ۰۵:۲۲ ب.ظ)zfmo نوشته شده توسط: سلام
ببخشید می شه مرتبه های زمانی مثال های زیر را برایم توضیح دهید ( با نماد های مجانبی)
[tex]T(n)=5T(n/5) {\frac{n}{logn}}[/tex]
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 رو با تغییر متغیر حل کنم ولی موفق نشدم. بعد از تغییر متغیر رابطه تبدیل به شکل زیر میشه:
[tex]n=2^k[/tex]
[tex]T(2^k) = T(2^{k-1}) T(2^{k-2}) T(2^{k-3}) 2^k[/tex]
[tex]F(k) = T(2^k) => F(k) = F(k-1) F(k-2) F(k-3) 2^k[/tex]
در اصل من توی حل کردن این رابطه‌ی آخری مشکل داشتم. سعی کردم با تکرار حلش کنم که به جای خوبی نرسیدم. ممنون می‌شم کمک کنید.
(۱۷ بهمن ۱۳۹۱ ۰۳:۵۶ ب.ظ)elahehab نوشته شده توسط: سلام، من تلاش کردم T(n)=T(n/2)+T(n/8)+T(n/4)+n رو با تغییر متغیر حل کنم ولی موفق نشدم.با استفاده از درخت بازگشت میشه خیلی خیلی راحت حلش کرد. حلش تو کتاب CLRS اومده