سوال اول :
خیر استثنای قضیه مستر نیست چون a, b برابر نیستند و جواب میشه گزینه چهار بر حسب حالت دوم قضیه.
و n^2lgn و n^2 هم مرتبه نیستند و n^2logn بزرگتره ولی به صورت چندجمله ای بزرگتر نیست. پس در یک log ضرب میشه.

سوال دوم هم قبلا بحث شده.
اگه لینکشو پیدا کردم میذارم

ممنون- ولی طبق کلید جواب گزینه ۳

سوال دوم هم گشتم ولی پیدا نکردم

سوال اول گزینه سه صحیحه. چون تابع f برابر با تتای n^log(a,b)logn هست پس T یا همون مرتبه زمانی میشه n^log(a,b)log^2n یا همون n^2*log2(n)
این که در قضیه اصلی بازگو شده و هیچ استثنایی هم درش نیست. منظورم قضیه دوم هست

اشتباه لپی بود!!
گزینه ۴ میشه ولی باز هم استثنا قضیه نیست.

یعنی شما n^2 و n^2LOGn رو هم مرتبه گرفتین؟

خیر.
دقت کنید تو پست ۲ توضیح دادم.

---

(۰۲ بهمن ۱۳۹۱ ۱۰:۴۰ ب.ظ)reza7788 نوشته شده توسط:  ممنون- ولی طبق کلید جواب گزینه ۳

سوال دوم هم گشتم ولی پیدا نکردم

اینجا بحث شده


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

الان به این لینکی داده بودید نگاه انداختم ولی جواب مشخصی نداره

(۰۳ بهمن ۱۳۹۱ ۱۲:۰۲ ب.ظ)egm1176 نوشته شده توسط:  ولی باز هم استثنا قضیه نیست.

از کجا باید فهمید که باید از استثناء قضیه مستر حل کنیم؟

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

(03 بهمن ۱۳۹۱ ۱۲:۰۲ ب.ظ)egm1176 نوشته شده توسط:  ولی باز هم استثنا قضیه نیست.

از کجا باید فهمید که باید از استثناء قضیه مستر حل کنیم؟

فکر کنم از همان قضیه اصلی که در کتاب سی ال آر اس گفته شده بریم درست است نه اون فرمولهایی که توی کتابای کنکوری اومده

(۰۴ بهمن ۱۳۹۱ ۱۲:۰۷ ق.ظ)reza7788 نوشته شده توسط:  الان به این لینکی داده بودید نگاه انداختم ولی جواب مشخصی نداره

ندیدید که سوال غلطه و حذف شده؟؟

پاسخ سوال ۵۱ :
میانگین : teta_n
بدترین : teta_nLgn
-----------------
توضیح :
با روش درهم سازی می توان عناصر تکراری را یافت.بهترین تابع درهم ساز در حالت میانگین میشه : teta_n
--
ابتدا یکی از دو آرایه رو مرتب می کنیم و با جستجوی دودویی ،عناصر آرایه ی دوم رو توی آرایه ی مرتب اولی پیدا می کنیم.
جستجو میشه lgn که اگه برای n عنصر تکرا کنیم میشه توی بدترین حالت :
teta_nlgn
------------------------------
این جوابی که دادم کامل هست و اصلا شک نکن.
طبق سنجش هم گزینه ی ۲ درسته
-------

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

۴۹ میشه ۳
۵۱ میشه ۲