ویرگول
ورودثبت نام
Arash
Arashعلاقه مند به علوم کامپیوتر
Arash
Arash
خواندن ۴ دقیقه·۷ سال پیش

Art Of Programming : #1 مسئله شماره

تو این مسئله درباره یافتن عنصر کمینه تو یه آرایه n عنصری غیر تکراری با اعداد مثبت که مرتب شدن (صعودی) اما بصورت خاصی این مرتب سازی انجام شده که اصطلاحا بهش میگن آرایه sorted rotated هست ، اینطوری میشه گفت که فرض کنید یه آرایه مرتب مثل 1,2,3,4,5,6 داریم بعد از دوبار چرخوندن این آرایه مثل میشه 5,6,1,2,3,4 .

ایده اول این هستش که با پیمایش خطی آرایه عنصر کمینه رو پیدا کنیم و این مسئله رو تو مرتبه بیگ اُ n حل کنیم اما سوال اینجاست که آیا میشه این مسئله رو تو مرتبه زمانی بهتر از خطی حل کرد ؟ کلا سوال هایی که راجع به ارائه یک راه حل بهتر هستش برمیگرده به اینکه چقدر شما با نمونه مسائل مختلف سر و کار دارید بطور مثال چه روش های حل مسئله مثل ( تقسیم و غلبه ، پویا ، حریصانه و ... ) رو می دونید آیا همیشه برای یافتن یک عدد تو آرایه شروع می کنید از ابتدا تا انتها دنبالش گشتن ؟ چقدر با مدل سازی های مختلف داده ها آشنا هستید ؟ به عبارت داده ساختارها رو چقدر می شناسید ؟ پس اگه دنبال این هستید که از پس این جور مسائل بربیاید باید مسئله های کلاسیکی که مطرح شدن و خیلی معروف هستن و شروع کنید به حل کردن و یجورایی با طرز فکر این راه حل ها آشنا بشید بعدش کم کم خودتون مدل فکری که دارید عوض میشه البته دنیای الگوریتم انتها نداره همیشه مسئله هایی هستن که واقعا ارائه یک راه حل بهینه براشون سخته ولی در کل به ما یه خط فکری خوبی میده که چطوری باید فکر کنیم.

خب حالا برسیم سراغ ایده ی حل این مسئله ، چیزی که من برای پیدا کردن یه عنصر اونم تو شرایطی که آرایه مرتب باشه به ذهنم میرسه استفاده از جستجوی دودویی هستش البته میدونم اینجا مرتب بودن به اون معنا که ما فکر میکنیم نیست اما این ارایه یه خاصیتی داره که بازم میشه از همین روش استفاده کرد ، بطور خلاصه من میگم در یک آرایه مرتب عنصر اولی کمینه هست چه خاصیتی داره ؟ همیشه از عنصرهای بعدی خودش کوچکتر هست حالا عنصرهای آرایه رو بچرخون باز این عنصر کمینه چه خاصیتی داره ؟ این عنصر علاوه بر اینکه از عنصرهای بعدی خودش کوچکتر هست از عنصر های قبلی خودش هم کوچکتر است ! بگذارید اینو با یه مثال شرح بدم : آرایه 1,2,3,4 عنصر 1 کمینه هست از 2و3و4 هم کوچکتر است حالا فرض کنید یک چرخش انجام بشه آرایه میشه 4,1,2,3 همچنان این عنصر از عناصر قبل و بعد خودش کوچکتر هست حالا ما باید به کمک جستجوی دودویی دنبال این عنصر باشیم و با یه شرط ساده برای هر عنصر بررسی کنیم که آیا عنصری وجود دارد که از قبل و بعد خودش کوچکتر باشد ؟

تو جستجوی دودویی عنصر میانه پیدا می کردیم الان هم باید همین کارو بکنیم ، پس اول میانه پیدا میشه اینطوری :

int mid = (from + to) / 2;

یعنی من میگم from و to اگه اندیس شروع و آخر آریه باشه mid میشه اندیس میانه .

بعد میام شرط زیر و برای این عنصر میانه چک میکنم :

if (array[mid] < array[mid + 1] && array[mid - 1] > array[mid]) { return array[mid]; }

حالا ممکنه این شرط برقرار باشه پس خود عنصر میانه همون کمینه است ، فرضا" اگه آرایه ورودی 4,1,2,3 باشه . میانه میشه عنصر 1 که دقیقا تو این شرط صدق میکنه !

قبل از این موارد یه چنتا حالت خاص رو لازم هستش بررسی کرده باشیم . اینکه آرایه تک عنصری باشه یا میانه ۰ حساب بشه

if (from == to) { return array[from]; } int mid = (to + from) / 2; if (mid == 0) { if (array[mid] < array[mid + 1]) { return array[mid]; } return array[mid + 1]; }

توضیحات کدهای بالا بنظرم دیگه آسون باشه براتون تو شرط اول گفتیم که اگه به یه ارایه تک عنصری رسیدیم خب همون عنصر کمینه هست و یکی و برگردون . دوم اینکه اگه میانه صفر بدست اومد یعنی به یه ارایه دو عضوی رسیدیم کافیه مینیمم اون دوتا برگردونیم

آخر سر باید روی آرایه بازگشتی بزنیم حالا اینکه عناصر بالای میانه باشه یا عناصر پایینش با یه مقایسه بدست میاد ، یعنی همون استراتژی که تو جستجوی دودویی بود اینجا استفاده میشه

if (array[mid] < array[to]) { return findMin(array, from, mid - 1); } return findMin(array, mid + 1, to);

اخر سر کدی که من نوشتم اینطوریه :

private static int findMin(int array[], int from, int to) { if (from == to) { return array[from]; } int mid = (to + from) / 2; if (mid == 0) { if (array[mid] < array[mid + 1]) { return array[mid]; } return array[mid + 1]; } if (array[mid] < array[mid + 1] && array[mid - 1] > array[mid]) { return array[mid]; } if (array[mid] < array[to]) { return findMin(array, from, mid - 1); } return findMin(array, mid + 1, to); }

یافتن عدد تو یه آرایه مرتب ( شبه مرتب) میتونه تو زمان بهتر از خطی هم حل بشه ، همین مسئله رو تعمیم بدید به یافتن عنصر کمینه ، بیشینه و ... مسئله های این مدلی باز هم هست بعدا اگه شد حل میکینم

اثبات مرتبه زمانی این الگوریتم هم آسونه :

T(n) = T(n/2) + teta(c)

کلا استراتژی حل با جستجوی دودویی اینطوری هست که یکسری عملیات روی عنصر میانه انجام میده بعدش طبق همون روی نیمه بالا یا پایین میانه بازگشتی میزنه تا به اون عنصر مورد نظر برسه

آرایه
۷
۱
Arash
Arash
علاقه مند به علوم کامپیوتر
شاید از این پست‌ها خوشتان بیاید