تالار گفتمان مانشت

(25 بهمن 1392 09:36 ق.ظ)ppp1486 نوشته شده توسط: [ -> ]درضمن اگه از راهی که شما خودتون فرمودید هم بریم T(n)=T(n/2)+n^2 اگه از طریق قضیه Master - Slave حلش کنیم هم به گزینه ۲ می رسیم

احتمالاً من پبر شدم! کران پایین این جمله $n^2$ هست. کران بالا هم در بدترین شرایط همون $cn^2$ هست. بنابراین گزینه $\theta(n^2)$ کاملاً درسته.

چرا دوستان میگن درخت minmax غلطه؟

درود بر همه دوستان سوال 198 و 199 رو چه گزینه ای زدید؟؟؟

من فکر کنم ۱۸۷ گزینه سه درست باشه. یعنی $O(n)$
روال کار هم اینطور باشه که:
با عناصر موجود یک Max Heap می‌سازیم.

هر بار بزرگ‌ترین عنصر این هیپ رو در logn حذف می‌کنیم و به یه آرایه‌ی دیگه اضافه می‌کنیم. این کار رو logn بار تکرار می‌کنیم و در نهایت اعداد رو خواهیم داشت. بعد در logn جمع این‌ها رو پیدا می‌کنیم. در کل میشه گفت هزینه برابر با $n+log^2n+logn=O(n)$ میشه.

البته ممکنه اشتباه کنم.

دقیقا یادم نیست اما در کتاب ۶۰۰ مسئله دکتر قدسی یه سوالی مشابه ۱۸۶ بود که جوابش شده بود $O(n)$
اما این سوال تا جایی که یادمه از تمرین‌های MIT بوده که در آنجا بحث $nlogn$ و... بود.