تاثیر الگوریتم در سرعت نرم افزار – مقایسه سرعت الگوریتم های جستجو

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

چه الگوریتم هایی برای جستجو وجود دارد؟

احتمالا اولین و ساده ترین الگوریتمی که به ذهن مان میرسید این است که ی کلمه جستجو شده را یک به یک با کلماتی که در دیکشنری داریم مقایسه کنیم. به این روش «جستجوی خطی» میگویند، این روش ساده، برای تعداد کلمات پایین به خوبی کار میکند اما در تعداد کلمات بالا این فرایند بسیار طولانی خواهد شد، آیا روش دیگری هم برای جستجو وجود دارد؟ به طور کلی دو الگوریتم معروف برای حل این مسئله وجود دارد :

• جستجوی خطی
• جستجوی دودویی

الگوریتم جستجوی خطی

همانطور که گفتیم الگوریتم جستجوی خطی به این روش است که ما کلمه مورد نظر خودمان را با تک تک کلمات موجود در لیست مقایسه میکنیم تا به نتیجه برسیم، الگوریتم به شکل زیر خواهد بود:

طبیعتا بررسی کردن کل کلمات یک دیکشنری کار زمان بر و بیهوده ای است و به راحتی میتوان گفت که این الگوریتم بهینه و سریع نیست، پس بهتر است با الگوریتم جستجوی دیگری آشنا شویم.

الگوریتم جستجوی دودویی (Binary Search)

جستجوی دودویی بسیار سریع تر از روش خطی عمل میکند، در این روش ما ابتدا کلمه ای را که در وسط دیکشنری قرار دارد پیدا میکنیم و آن کلمه را با کلمه مورد نظر خودمان مقایسه میکنیم اگر کلمه مورد نظر را پیدا کردیم که نتیجه روشن است، اما اگر پیدا نکردیم باید ببینیم که کلمه مورد نظر در ترتیب الفبا بعد از آن کلمه است یا قبل از آن. اگر بعد از آن باشد ما نیمه اول دیکشنری را کنار میگذاریم و مجددا نیمه دوم دیکشنری را به دو بخش تقسیم میکنیم و همان روند را تکرار میکنیم، اگر هم کلمه مورد نظر قبل از کلمه ای که پیدا کردیم باشد نیمه دوم دیکشنری را کنار میگذاریم و نیمه اول را به دو بخش تقسیم میکنیم و…

فلوچارت جستجوی دودویی به روش زیر خواهد بود:

نکته مهمی که درباره جستجوی دودویی وجود دارد این است که ای ن روش تنها برای لیست هایی ممکن است که مرتب شده باشند. اگر ما لیستی غیر مرتب داشته باشیم به ناچار باید از روش خطی استفاده کنیم که به شدت زمان بر است.

چطور بفهمیم که یک الگوریتم سریع تر از دیگری است؟

تا اینجا فهمیدیم که انتخاب الگوریتم مناسب تاثیر خیلی زیادی بر سرعت نرم افزار دارد، اما از کجا بفهمیم که در هر موردی چه الگوریتمی سریع تر است؟ قاعده کلی این است که «الگوریتمی که تعداد عملیات کمتری انجام دهد الگوریتم سریع تری است» برای مثال ما برای پیدا کردن یک کلمه در یک دیکشنری چند هزار کلمه ای با روش خطی باید هزاران عملیات انجام دهیم اما با روش دودویی کمتر از 50 عملیات خواهیم داشت. اما باید توجه داشت که این اختلاف سرعت در اعداد بزرگ خودش را نشان میدهد و در اعداد کوچک تر، تمام الگوریتم ها سرعت های نزدیک بهم دارند. معمولا برای نشان دادن سرعت الگوریتم از علامت O بزرگ استفاده میشود که روش محاسبه و استفاده از آن را حتما در مقالات بعدی توضیح خواهیم داد.

نتیجه گیری

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

خیلی ممنون از اینکه وقت گذاشتید و این مقاله رو مطالعه کردید، ممنون میشم نظرتون رو بهم بگید.