سوال ۴-۴/۳ CLRS ویرایش دوم- تعیین حد بالای رابطه بازگشتی - نسخه‌ی قابل چاپ

سوال ۴-۴/۳ CLRS ویرایش دوم- تعیین حد بالای رابطه بازگشتی - دیانا - ۱۱ بهمن ۱۳۹۱ ۱۱:۱۹ ق.ظ سلام به دوستان عزیز یک سوال در مورد یافتن کران بالای تابع t(n)=4t(n/2)+n^2 logn دارم. در یک جا جوابش طبق روش درختی n^2 logn گفته شده است ولی در CLRS طبق سوال ۴/۴-۲ باید n^2 log^2n شود. عکس های هر دو را هم پیوست کردم. از دوستان خواهشمندم مرا راهنمایی کنند.

سوال ۴-۴/۳ CLRS ویرایش دوم- تعیین حد بالای رابطه بازگشتی - ۸Operation - 11 بهمن ۱۳۹۱ ۱۲:۰۸ ب.ظ حالت پیشرفته مستره!همون CLRS درسته!

سوال ۴-۴/۳ CLRS ویرایش دوم- تعیین حد بالای رابطه بازگشتی - دیانا - ۱۱ بهمن ۱۳۹۱ ۱۲:۲۲ ب.ظ خیلی ممنونم

سوال ۴-۴/۳ CLRS ویرایش دوم- تعیین حد بالای رابطه بازگشتی - csharpisatechnology - 13 بهمن ۱۳۹۱ ۰۲:۳۶ ب.ظ قضیه ی master اینه : مثالی از یک حالت خاص : [tex]T(n)= 2T(n/2) lgn![/tex] ببین سمت چپ میشه n به توان لگاریتم ۲ در مبنای ۲ که جواب میشه teta_n سمت راست هم میشه : teta_nLgn ---- در اینجا حالت خاص رو داریم : اینجا چون f(n در [tex]lg^k(n)[/tex] ضرب شده ابتدا [tex]lg^k(n)[/tex] رو حذف کن میشه: سمت چپ میشه o_n سمت راست هم میشه o_n چون مساوی شدن پس سمت راست یعنی f(n) رو lgn ضرب می کنی میشه nlgn --- حالا اون چیزی که حذف کرده بودیم یعنی [tex]lg^k(n)[/tex] رو دوباره درش ضرب کن میشه : [tex]nlg^{k 1}(n)[/tex] [tex]nlg^{2}(n)[/tex] --------- در حالت کلی یک حالت داریم به اسم حالت تعمیم: [tex]t(n)=aT(\frac{n}{b}) f(n)[/tex] اگر در روش قضیه ی اصلی داشته باشیم : [tex]f(n)\varepsilon \theta(n^{log_{b}^{a}})lg^k{n}[/tex] و k>=0 باشد داریم: [tex]T(n)\varepsilon \theta(n^{log_{b}^{a}})lg^{k 1}{n}[/tex] ---------------------- مثال : [tex]T(n)=2t(n/2) nlgn=\theta(nlg^2n)[/tex] مثال بعدی: [tex]T(n)=4t(n/2) n^2lgn=\theta(n^2lg^2n)[/tex] ----------------------- اینم حل سوال شما: [tex]t(n)=4t(n/2) nlg(n!)=4t(n/2) n^2 lgn=\theta(n^2lg^2n)[/tex] شبیهشو اینجا حل کردم : مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.