انجمنصفحه اولجستجوی انجمن

[nfe89]

دوستای خوبم این مسئله خیلی ساده‌تر از اینه که فکر میکنید اصلن نیاز به این محاسبات و logn و این صحبتها نیست!
ببینید با همون الگوریتمی که دوستمون در پست دوم گفتن:

تو هر مرحله میانه‌ها رو مقایسه میکنیم
**مساوی که نخواهد شد. چون اعداد متمایزند. پس یکی بزرگتره یکی کوچکتر.
از اون آرایه که میانش بزرگتره، اعداد بعد از میانشو حذف میکنیم.
از اون آرایه که کوچتره هم اعداد قبل میانشو حذف میکنیم.

الان دوتا آرایه داریم با نصف اندازه آرایه های قبلی.
در ضمن این دو آرایه جفتشون مرتب هستن چون فقط به قسمت ازشون برداشته شده.

پس شرایط مسئله اولیه که تعداد درایه های مساوی و مرتب بودن هر دو آرایه هست توشون صدق میکنه.
از طرفی چون تو هر مرحله اون تعدادی که حذف میشن نصفشون بزرگتر از میانه کل هستند و نصفشون کوچکتر هستن‌، پس میانه اصلی هنوز هم وسط قرار داره.( در واقع اینطوری ثابت میشه میانه حساب شده تو مرحله i همون میانه حساب شده در مرحله i-1 هست.)
و این مؤید درستی پاسخ نهایی الگوریتم هست.

سوال تعداد دسترسی به درایه‌ها رو خواسته. که ما تو هر مرحله ۲ تا داریم چون دو تا میانه رو دست میزنیم. (میانه تو آرایه مرتب عنصر وسط آرایست) و بعد آرایه‌ها نصف میشن.
پس بصورت بازگشتی داریم: t(2n) = t(n)+2
گزینه اول.