سلام من یه سوالی رو دیدم و به این شکل تا ی جایی حلش کردم ولی بقیشو نتونستم ادمه بدم
ممنون میشم کسی حلش کنه
میخوام اخر کار بدترین حالت پیچیدگی زمانیشو به دست بیارم
[tex]T(n)=2T(\frac{3n}{3})-\log\: n\: \Longrightarrow\: n=b^k\: \Longrightarrow\: n=3^k\: \Longrightarrow\: T(3^k)=2\: T (3^k)\: -\log\: 3^k\: \Longrightarrow\: T(3^k)=t_k\: \Longrightarrow\: t_k=2t_k\: -klog3\: [/tex]
(۰۹ خرداد ۱۳۹۵ ۰۹:۰۴ ب.ظ)kamal3401 نوشته شده توسط: سلام من یه سوالی رو دیدم و به این شکل تا ی جایی حلش کردم ولی بقیشو نتونستم ادمه بدم
ممنون میشم کسی حلش کنه
میخوام اخر کار بدترین حالت پیچیدگی زمانیشو به دست بیارم
لتکس رو به نظر اشتباه نوشتید که درستش این هست:
[tex]T(n)=2T(\frac{3n}{3})-\log\:n\:\Longrightarrow\:n=b^k\:\Longrightarrow\:n=3^k\:\Longrightarrow\:T(3^k)=2\:T\:(3^k)\:-\log\:3^k\:\Longrightarrow\:T(3^k)=t_k\:\Longrightarrow\:t_k=2t_k\:-klog3\:[/tex]
بعد مطمئن هستید سوال درست هست؟ چون اگه (T(n رو بیارید اینور و Log رو ببرید اونور، جواب میشه [tex]T(n)=\log(n)[/tex]
(۰۹ خرداد ۱۳۹۵ ۰۹:۲۰ ب.ظ)behnam5670 نوشته شده توسط:(09 خرداد ۱۳۹۵ ۰۹:۰۴ ب.ظ)kamal3401 نوشته شده توسط: سلام من یه سوالی رو دیدم و به این شکل تا ی جایی حلش کردم ولی بقیشو نتونستم ادمه بدم
ممنون میشم کسی حلش کنه
میخوام اخر کار بدترین حالت پیچیدگی زمانیشو به دست بیارم
لتکس رو به نظر اشتباه نوشتید که درستش این هست:
[tex]T(n)=2T(\frac{3n}{3})-\log\: n\: \Longrightarrow\: n=b^k\: \Longrightarrow\: n=3^k\: \Longrightarrow\: T(3^k)=2\: T\: (3^k)\: -\log\: 3^k\: \Longrightarrow\: T(3^k)=t_k\: \Longrightarrow\: t_k=2t_k\: -klog3\: [/tex]
بعد مطمئن هستید سوال درست هست؟ چون اگه (T(n رو بیارید اینور و Log رو ببرید اونور، جواب میشه [tex]T(n)=\log(n)[/tex]
بله جوابش همون لوگ ان میشه! خیلی سوال بی ربطی بود برا همین به شک انداخت
ممنون از راهنمایی