(۱۱ آبان ۱۳۹۲ ۰۱:۱۷ ق.ظ)mohammad-a نوشته شده توسط:  

(10 آبان ۱۳۹۲ ۱۰:۲۴ ب.ظ)adel4 نوشته شده توسط:  سلام.
ببخشید میشه الگوریتم این مسله رو بنویسید. هزینش باید logn بشه . از راه تقسیم وغلبه حل میشه. هر چی میانه ها رو با هم مقایسه میکنم نمیشه
دو ارایه X(1………..n) و Y(1……………..n) مرتب شده اند . سریع ترین الگوریتم برای یافتن میانه ۲n عضو ارایه های x , y کدام است ؟

الگوریتم یافتن میانه که در O(n) هستش. اینجا آرایه‌ها مرتب هستند و از این بابت مسئله‌ای نداریم.

چون آرایه‌ها مرتب هستند، عنصر میانه‌ی هر آرایه را در O(1 می‌توانیم بدست بیاریم و مقایسه‌ی این دو را هم در O(1 انجام بدیم.

هنگام مقایسه‌ی عناصر میانه ۳ حالت خواهیم داشت:
۱. میانه‌ی هر دو آرایه یکسان هستند. در اینصورت همین پاسخ ماست.
۲. میانه‌ی آرایه‌ی اول کوچکتر از میانه‌ی آرایه‌ی دوم است.
۳. میانه‌ی آرایه‌ی دوم کوچکتر از آرایه‌ی اول است.

برای حالت دوم، از عنصر ابتدای آرایه تا عنصر ماقبل میانه را کنار می‌گذاریم. عکس این کار را برای آرایه‌ی دوم انجام می‌دهیم.
در حالت سوم، کاری که در بالا انجام دادیم رو برعکس اجرا می‌کنیم.

این کار رو آنقدر انجام می‌دهیم که یا به چیزی که در مرحله‌ی اول گفته شد برسیم؛ یا اینکه تعداد عناصر آرایه یک عدد شود. همین می‌شود میانه‌ی دو آرایه.

مرتبه‌ی این الگوریتم به شکل زیر است:
[tex]\\ T(2n)=T(n) O(1)\in O(logn)[/tex]