دو ارایه X(1………..n) و Y(1……………..n) مرتب شده اند . سریع ترین الگوریتم برای یافتن میانه ۲n عضو ارایه های x , y کدام است ؟
۱- روش استفاده از ادغام که O(n) زمان نیاز دارد
۲- روش استفاده از ادغام که O(logn) زمان نیاز دارد
۳- یک الگوریتم تقسیم و حل است که نمونه های n تایی ان به زیر نمونه های n/2 تایی تبدیل می کند (رادیکال n O( زمان نیاز دارد
۴- یک الگوریتم تقسیم و حل است که نمونه های n تایی ان به زیر نمونه های n/2 تایی تبدیل می کند O(log n )زمان نیاز دارد
جواب ۴ چراااا ؟؟؟؟؟؟
هیچ توضیح تشریحی نداده .یعنی اینقدر واضح ؟
سلام.
ببینید گفته که هردو آرایه مرتب شده اند، پس برای جستجو می تونیم از الگوریتم جستجوی دودویی استفاده کنیم. (اگه مرتب نمی بودن قضیه فرق می کرد). عنصر وسط یکی از آرایه ها رو می تونیم با یک جستجو انجام بدیم و با عنصر وسط آرایه دومی مقایسه کنیم، در صورتی که از اون بزرگتر بود آرایه دومی به دو قسمت مساوی تقسیم میشه و برای قسمت بالای آرایه همین عمل رو تکرار می کنیم، اما اگه کوچیکتر باشه قسمت پایین آرایه دومی رو جستجو می کنیم.
در هرصورت مرتبه اون برابر هست با مرتبه جستجوی دودویی که میشه O(logn
جواب ۴هم منظورش از تقسیم کردن n به n/2 همین است.
موفق باشید.
با استفاده از درخت قرمز-سیاه اعمال درج و حذف و جستجو میشه lgn
--------
منبع : کتاب پردازش
ببخشید .میشه الگوریتم پیدا کردن میانه ۲n در دو آرایه رو بنویسید .هر کاری میکنم نمیتونم بنویسم.