صفحه‌ها: ۱ ۲
(۲۵ بهمن ۱۳۹۲ ۰۹:۳۶ ق.ظ)ppp1486 نوشته شده توسط: درضمن اگه از راهی که شما خودتون فرمودید هم بریم T(n)=T(n/2)+n^2 اگه از طریق قضیه Master - Slave حلش کنیم هم به گزینه ۲ می رسیم
احتمالاً من پبر شدم! کران پایین این جمله $n^2$ هست. کران بالا هم در بدترین شرایط همون $cn^2$ هست. بنابراین گزینه $\theta(n^2)$ کاملاً درسته.
چرا دوستان میگن درخت minmax غلطه؟
درود بر همه دوستان سوال ۱۹۸ و ۱۹۹ رو چه گزینه ای زدید؟؟؟
من فکر کنم ۱۸۷ گزینه سه درست باشه. یعنی $O(n)$
روال کار هم اینطور باشه که:
با عناصر موجود یک Max Heap می‌سازیم.
هر بار بزرگ‌ترین عنصر این هیپ رو در logn حذف می‌کنیم و به یه آرایه‌ی دیگه اضافه می‌کنیم. این کار رو logn بار تکرار می‌کنیم و در نهایت اعداد رو خواهیم داشت. بعد در logn جمع این‌ها رو پیدا می‌کنیم. در کل میشه گفت هزینه برابر با $n+log^2n+logn=O(n)$ میشه.
البته ممکنه اشتباه کنم.
دقیقا یادم نیست اما در کتاب ۶۰۰ مسئله دکتر قدسی یه سوالی مشابه ۱۸۶ بود که جوابش شده بود $O(n)$
اما این سوال تا جایی که یادمه از تمرین‌های MIT بوده که در آنجا بحث $nlogn$ و... بود.