۰
subtitle
ارسال: #۱
تست کامپیوتر ۸۵ (میانه ۲N عنصر)
دو ارایه 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(n) زمان نیاز دارد
۲- روش استفاده از ادغام که O(logn) زمان نیاز دارد
۳- یک الگوریتم تقسیم و حل است که نمونه های n تایی ان به زیر نمونه های n/2 تایی تبدیل می کند (رادیکال n O( زمان نیاز دارد
۴- یک الگوریتم تقسیم و حل است که نمونه های n تایی ان به زیر نمونه های n/2 تایی تبدیل می کند O(log n )زمان نیاز دارد
جواب ۴ چراااا ؟؟؟؟؟؟
هیچ توضیح تشریحی نداده .یعنی اینقدر واضح ؟
۰
ارسال: #۲
تست کامپیوتر ۸۵ (میانه ۲N عنصر)
سلام.
ببینید گفته که هردو آرایه مرتب شده اند، پس برای جستجو می تونیم از الگوریتم جستجوی دودویی استفاده کنیم. (اگه مرتب نمی بودن قضیه فرق می کرد). عنصر وسط یکی از آرایه ها رو می تونیم با یک جستجو انجام بدیم و با عنصر وسط آرایه دومی مقایسه کنیم، در صورتی که از اون بزرگتر بود آرایه دومی به دو قسمت مساوی تقسیم میشه و برای قسمت بالای آرایه همین عمل رو تکرار می کنیم، اما اگه کوچیکتر باشه قسمت پایین آرایه دومی رو جستجو می کنیم.
در هرصورت مرتبه اون برابر هست با مرتبه جستجوی دودویی که میشه O(logn
جواب ۴هم منظورش از تقسیم کردن n به n/2 همین است.
موفق باشید.
ببینید گفته که هردو آرایه مرتب شده اند، پس برای جستجو می تونیم از الگوریتم جستجوی دودویی استفاده کنیم. (اگه مرتب نمی بودن قضیه فرق می کرد). عنصر وسط یکی از آرایه ها رو می تونیم با یک جستجو انجام بدیم و با عنصر وسط آرایه دومی مقایسه کنیم، در صورتی که از اون بزرگتر بود آرایه دومی به دو قسمت مساوی تقسیم میشه و برای قسمت بالای آرایه همین عمل رو تکرار می کنیم، اما اگه کوچیکتر باشه قسمت پایین آرایه دومی رو جستجو می کنیم.
در هرصورت مرتبه اون برابر هست با مرتبه جستجوی دودویی که میشه O(logn
جواب ۴هم منظورش از تقسیم کردن n به n/2 همین است.
موفق باشید.
ارسال: #۳
RE: تست کامپیوتر ۸۵ (میانه ۲N عنصر)
ببخشید .میشه الگوریتم پیدا کردن میانه ۲n در دو آرایه رو بنویسید .هر کاری میکنم نمیتونم بنویسم.
۰
ارسال: #۴
تست کامپیوتر ۸۵ (میانه ۲N عنصر)
با استفاده از درخت قرمز-سیاه اعمال درج و حذف و جستجو میشه lgn
--------
منبع : کتاب پردازش
--------
منبع : کتاب پردازش
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close