g = چند جمله ای

[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]

T(n)=2T(n/2)+nlogn
به عقیده من فرآیند جواب به این صورت میشه:
T(n/2)+T(n/2)+nlogn
پس در نهایت داریم:
n+nlogn
که میشه خود (O(nlogn

(۱۷ بهمن ۱۳۹۰ ۱۰:۲۳ ب.ظ)amino22 نوشته شده توسط:  

(03 آذر ۱۳۹۰ ۱۱:۵۹ ق.ظ)mar236 نوشته شده توسط:  

T(n)=2T(n/2)+nlogn
به عقیده من فرآیند جواب به این صورت میشه:
T(n/2)+T(n/2)+nlogn
پس در نهایت داریم:
n+nlogn
که میشه خود (O(nlogn

نه روند کار غلطه‌، روند صحیح در بالا بچه‌ها توضیح دادن.

[tex]T(n)=T(n-1) T(n-1)=2*T(n-1)\epsilon O(2^{n})[/tex]


که توی کتاب مقسمی اشتباها دومی رو از مرتبه (O(n گرفته!!!!

برای حل رابطه بازگشتی از طریق درخت بازگشت به این نکته دقت کنید:
ارتفاع درخت (h) توسط فرمول

محاسبه میشود که در آن b اندازه زیر مسائل است.
یادآوری:

به نکته ظریف زیر دقت کنید:

------------------


بچه‌ها شما هم شرکت کنید دیگه

یه نکته جالب برای حل روابط بازگشتی:

تذکر‌: در این نکته 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

(۱۴ آبان ۱۳۹۰ ۱۲:۲۶ ق.ظ)mojgan نوشته شده توسط:  

(21 آذر ۱۳۸۹ ۰۱:۵۶ ب.ظ)Masoud05 نوشته شده توسط:  با سلا م به دوستان‌، یه فایل upload براتون کردم که سوالات دانشگاه MIT هست جواب هم کنارش هست . خیلی فوق العاده هست . حتماً حتماً حتماً دانلود کنید


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

سلام
مرسی از این همه همت
من نتونستم این رو دانلود کنم
دقیقا رو کدو گزینه برم
چون هر جا کلیلک می کنم یا صفحه‌ی دیگه باز می شه یا با پسوند اچ تی‌ام ال ذخیره می شه
ممنون

in quiz haye danesh gahe mit too site khode daneshgah hast berid az oonja download konid

سلام
من یه سوال دارم؟؟؟؟؟
سوال ۸۹ ای تی:

۴f(n/2)+n^2logn

به نظر من میشه n^2logn ولی جواب زده n^2 (log〖n)〗^۲
من کتوجه نمی شم چرا مکه k همون ۲ نیست پس باید بگیم b^k=a و جواب میشه n^2logn ؟؟
ممکنه کسی کمک کنه؟؟

(۰۳ آذر ۱۳۸۹ ۱۲:۴۱ ق.ظ)۵۴m4n3h نوشته شده توسط:  

یکی از تمرین های CLRS هست که توی کتاب یوسفی جوابش بود، به نظرم خیلی مفیده!

آیا منظور همان ترتیب مرتبه زمانی (بیگ او) این توابع است؟
می شه سوال رو بنویسید؟

(۱۶ فروردین ۱۳۹۱ ۰۱:۱۵ ق.ظ)fa_karoon نوشته شده توسط:  آیا منظور همان ترتیب مرتبه زمانی (بیگ او) این توابع است؟
می شه سوال رو بنویسید؟

علامت کوچکتر که گذاشته یعنی small o پس قطعا برای Big O هم درسته .