صفحه‌ها: ۱ ۲
برای شروع:
نکته:
n^2+log n از مرتبه تتا n^2هست اماn^2*logn نه
[tex]T(n)=T(n-1) T(n-1)=2*T(n-1)\epsilon O(2^{n})[/tex]
که توی کتاب مقسمی اشتباها دومی رو از مرتبه (O(n گرفته!!!!
برای حل رابطه بازگشتی از طریق درخت بازگشت به این نکته دقت کنید:
ارتفاع درخت (h) توسط فرمول [attachment=95]
محاسبه میشود که در آن b اندازه زیر مسائل است.
یادآوری:
[attachment=97]
یکی از تمرین های CLRS هست که توی کتاب یوسفی جوابش بود، به نظرم خیلی مفیده!
به نکته ظریف زیر دقت کنید:
------------------
[attachment=119]
بچه‌ها شما هم شرکت کنید دیگه
g = چند جمله ای
یه نکته جالب برای حل روابط بازگشتی:
تذکر: در این نکته o کوچک داریم. هر چند که برای O بزرگ هم صحیح هست . اما با o کوچک به این نکته پی میبریم که مقدار سمت چپ عبارت اکیداً کوچکتر هست.
با سلا م به دوستان، یه فایل upload براتون کردم که سوالات دانشگاه MIT هست جواب هم کنارش هست . خیلی فوق العاده هست . حتماً حتماً حتماً دانلود کنید
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام . یه سوال جالب از جزوه سید جوادی( اگه بتونم نکات جالبش رو براتون میزارم)
برای ۴ خانه در نظر بگیرید جواب میشه ۱۳ .چرا؟ فرض کنید ۴ بیت داریم (۴ خانه) که هر یک ۲ مقدار می تواند داشته باشد پس ۴ ^۲= ۱۶ حالت داریم اما ۳ حالت غیر مجاز داریم( ۴ خانه سفید - ۳ خانه اول سفید - ۳ خانه آخر سفید) پس ۳-۱۶ تعداد کل حالات میشه
میتونید با رابطه بازگشتی داده شده اینو رو نشان بدین
نکته در مورد قضیه اصلی:
در بعضی موارد نمی توان از قضیه اصلی استفاده کرد مانند مثال های زیر:
۱) T(n)=2T(n/2)+nlogn
T(n)=2T(n/2)+n/logn(2
زیرا در مورد ۱ علیرغم اینکه با استفاده از قضیه اصلی n=O(nlognولی چون به صورت چندجمله ای بزرگتر نیست پس نمی توان از قضیه اصلی استفاده کرد.
در مورد ۲ هم n/logn=O(n ولی حاصل تقسیم تابع بزرگتر بر کوچکتر چند جمله ای نیست پس از این قضیه نمی توان استفاده کرد .
منبع: صفحه ۹۸CLRS
[tex]n^{k}=O((logn)^{logn})[/tex]
این رو یکجا خوندم ولی دلیلش رو نمیدونم اما فکر کنم عدد بگذارید دلیلش رو بفهمید!
(۱۴ بهمن ۱۳۸۹ ۰۸:۵۵ ب.ظ)afagh1389 نوشته شده توسط: [tex]n^{k}=O((logn)^{logn})[/tex]
این رو یکجا خوندم ولی دلیلش رو نمیدونم اما فکر کنم عدد بگذارید دلیلش رو بفهمید!
با توجه به این نکته که: [tex]{\color{red} a}^{\log {\color{blue}b}}={\color{blue} b}^{\log {\color{red} a}}[/tex]
[tex]{\color{red} \log n}^{\log {\color{blue} n}}={\color{blue} n}^{\log {\color{red} \log n}}[/tex]
جواب هر رابطه بازگشتی به فرم [tex]T(n)=T(\alpha n) T((1-\alpha) n) \Theta (n)[/tex] به طوری که [tex]\alpha[/tex] یک عدد ثابت و در محدوده [tex]0<\alpha <1[/tex] است برابر است با [tex]T(n)=\Theta (nlgn)[/tex]
خیلی راحت میشه با درخت بازگشتی اثباتش کرد
(۱۴ آبان ۱۳۹۰ ۱۲:۲۶ ق.ظ)mojgan نوشته شده توسط:لینکش رو چک کردم، درست بود. البته اینطور که آقا فرداد میگفت ظاهرا توی بسته مانشت هم هست . من این فایل بهمراه چند تا فایل آموزشی مستقیما از سایت اصلی گرفتم.(21 آذر ۱۳۸۹ ۰۱:۵۶ ب.ظ)Masoud05 نوشته شده توسط: با سلا م به دوستان، یه فایل upload براتون کردم که سوالات دانشگاه MIT هست جواب هم کنارش هست . خیلی فوق العاده هست . حتماً حتماً حتماً دانلود کنید
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام
مرسی از این همه همت
من نتونستم این رو دانلود کنم
دقیقا رو کدو گزینه برم
چون هر جا کلیلک می کنم یا صفحه‌ی دیگه باز می شه یا با پسوند اچ تی‌ام ال ذخیره می شه
ممنون