چرا بعضی جاها نمیشه از قضیه اصلی استفاده کرد؟
[tex]T(n)=2T(\frac{n}{2}) \frac{n}{logn}[/tex]
در مثال بالا گفته چون مرتبه بزرگی [tex]n^{log{_{b}}^{a}}[/tex] از F(n) بصورت چند جمله ای نیست پس نمی توان از قضیه اصلی استفاده کرد!!!
یعنی چی بصورت چند جمله ای نیست؟
آها متوجه شدم یعنی n/logn
چند جمله ای نیست درسته؟
حالا تنها راه حلش از طریق درخته؟
(۲۰ مهر ۱۳۹۰ ۰۱:۳۷ ب.ظ)پشتکار نوشته شده توسط: آها متوجه شدم یعنی n/logn
چند جمله ای نیست درسته؟
حالا تنها راه حلش از طریق درخته؟
سلام دوست مانشتی:
آره درسته چون fnباید چندجمله ای باشه که اینجا نیست.به غیر از درخت با جایگذاری هم میشه حلش کرد.
(۲۰ مهر ۱۳۹۰ ۰۲:۰۱ ب.ظ)khavar_1365 نوشته شده توسط:(20 مهر ۱۳۹۰ ۰۱:۳۷ ب.ظ)پشتکار نوشته شده توسط: آها متوجه شدم یعنی n/logn
چند جمله ای نیست درسته؟
حالا تنها راه حلش از طریق درخته؟
سلام دوست مانشتی:
آره درسته چون fnباید چندجمله ای باشه که اینجا نیست.به غیر از درخت با جایگذاری هم میشه حلش کرد.
میشه بنویسید با جایگذاری چطوری حل میشه؟
(۲۰ مهر ۱۳۹۰ ۰۳:۰۲ ب.ظ)پشتکار نوشته شده توسط:(20 مهر ۱۳۹۰ ۰۲:۰۱ ب.ظ)khavar_1365 نوشته شده توسط:(20 مهر ۱۳۹۰ ۰۱:۳۷ ب.ظ)پشتکار نوشته شده توسط: آها متوجه شدم یعنی n/logn
چند جمله ای نیست درسته؟
حالا تنها راه حلش از طریق درخته؟
سلام دوست مانشتی:
آره درسته چون fnباید چندجمله ای باشه که اینجا نیست.به غیر از درخت با جایگذاری هم میشه حلش کرد.
میشه بنویسید با جایگذاری چطوری حل میشه؟
فقط راهنمایی هم بکنید کافیه!
فکر کنم کار سختیه نه؟
(۲۰ مهر ۱۳۹۰ ۰۲:۰۱ ب.ظ)khavar_1365 نوشته شده توسط:(20 مهر ۱۳۹۰ ۰۱:۳۷ ب.ظ)پشتکار نوشته شده توسط: آها متوجه شدم یعنی n/logn
چند جمله ای نیست درسته؟
حالا تنها راه حلش از طریق درخته؟
سلام دوست مانشتی:
آره درسته چون fnباید چندجمله ای باشه که اینجا نیست.به غیر از درخت با جایگذاری هم میشه حلش کرد.
وقتی می گیم می شه از قضیه اصلی استفاده کرد ، به این معنا نیست که f حتما باید چند جمله ای باشه.
یعنی ممکنه f چند جمله ای هم نباشه ولی قضیه اصلی رو بشه استفاده کرد .
اون شرایطی که برای قضیه اصلی هست نمیگه که f باید چند جمله ای باشه . بلکه می گه g از f بصورت چند جمله ای بزرگتر (یاکوچکتر )باشه. یا اینکه مرتبه fو g برابر باشه.
و شما اگه بتونید نحوه کار با اون اپسیلون رو در شرایط قضیه اصلی یاد بگیرید، ان شاء الله حله.
موفق باشید.
سلام
این توابع رو میشه با قضیه اصلی حل کرد؟؟ اگه میشه جوابش چی میشه؟
T(n)=4T(√n/3)+log^2 n
T(n)=2T(n/2)+nlogn
کسی نیست کمک کنه؟؟!!!
اولی رو با تغییر متغیر میشه حل کرد که جوابش فکر کنم [tex]\log^{2} n\log \log n[/tex] میشه
دومی هم حالت خاصی هست که با قضیه Master حل نمیشه و حالت های خاصش رو تو کتاب مقسمی گفته آخرای فصل دوم که جوابش فکر کنم میشه [tex]n\log^{2} n[/tex]
اینجا هم جواب سوالاتون هست:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۳۰ مرداد ۱۳۹۱ ۱۲:۲۲ ب.ظ)ali نوشته شده توسط: اولی رو با تغییر متغیر میشه حل کرد که جوابش فکر کنم [tex]\log^{2} n\log \log n[/tex] میشه
دومی هم حالت خاصی هست که با قضیه Master حل نمیشه و حالت های خاصش رو تو کتاب مقسمی گفته آخرای فصل دوم که جوابش فکر کنم میشه [tex]n\log^{2} n[/tex]
آخه تو کتاب clrsنوشته که نمیشه این کار رو واسه دومی انجام داد ولی مقسمی همین رو حلش کرده و به همین جوابی که گفتین رسیده!!!!!!! به کدوم باید توجه کرد؟؟؟؟؟؟؟ clrs یا مقسمی؟؟؟؟؟؟
تو کنکور مهم نیست کی چی گفته ، مهم اینه که با سادترین راه به جواب نهایی برسی ، حالا می خواد CLRS گفته باشه یا مقسمی
(۳۰ مرداد ۱۳۹۱ ۰۲:۲۴ ب.ظ)ali نوشته شده توسط: تو کنکور مهم نیست کی چی گفته ، مهم اینه که با سادترین راه به جواب نهایی برسی ، حالا می خواد CLRS گفته باشه یا مقسمی
یعنی این که مقسمی حل کرده حالت خاص از قضیه اصلی هست؟؟
آره، به این نتیجه رسیده اگه شرایط مسله a ,b مساوی باشه و (f(nبزرگتر از (t(n باشه اما نه بصورت چندجمله ای باید اینطوری حلش کرد
سلام
این توابع چطوری با قضیه اصلی حل میشه؟؟؟؟؟
T(n)=√nT(√n)+n
T(n)=3T(n/3)+n/log n
(۰۳ شهریور ۱۳۹۱ ۰۶:۳۵ ب.ظ)mohsen_4050 نوشته شده توسط: سلامسوال اول
این توابع چطوری با قضیه اصلی حل میشه؟؟؟؟؟
T(n)=√nT(√n)+n
T(n)=3T(n/3)+n/log n
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سوال دوم برای حالت T(n)=2T(n/2)+n/log n
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.