مبانی الگوریتم – آموزش ساختمان داده ها

مبانی الگوریتم

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

برخی مباحث مهم الگوریتم از دیدگاه ساختمان داده عبارت اند از:

• جستجو (Search): الگوریتمی برای جستجوی یک آیتم در ساختمان داده.
• مرتب سازی بر اساس (Sort): الگوریتمی برای مرتب کردن موارد در یک نظم خاص.
• وارد کردن (Insert): الگوریتمی برای قرار دادن آیتم در ساختمان داده.
• به روز رسانی (Update): الگوریتم برای به روز رسانی یک آیتم موجود در ساختمان داده.
• حذف(Delete): الگوریتمی برای حذف یک آیتم موجود در ساختمان داده.

ویژگی های یک الگوریتم

الگوریتم ها دارای ویژگی های خاصی هستند. از این رو نمی توان هر روشی را یک الگوریتم نامید. در زیر ویژگی های یک الگوریتم را مشاهده می کنید:

• یکپارچگی: الگوریتم باید واضح و یکنواخت باشد. ورودی/خروجی و مراحل آن باید واضح و دارای یک معنی باشند.
• ورودی: یک الگوریتم باید دارای ۰ یا چند ورودی باشد.
• خروجی: یک الگورتیم حداقل باید یک خروجی منطبق با خروجی مورد نظر داشته باشد.
• محدودیت: الگوریتم باید بعد از انجام تعداد محدودی از مراحل پایان یابد.
• انجام پذیر: امکان انجام آن با منابع موجود، وجود داشته باشد.
• مستقل: مراحل مختلف یک الگوریتم نباید به یک زبان برنامه نویسی خاص وابسته باشند.

چگونگی نوشتن یک الگوریتم

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

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

مثال

مثال زیر نحوه نوشتن یک الگوریتم برای یک مسئله ساده را نشان می دهد.

مسئله: طراحی یک الگوریتم برای جمع دو عدد نمایش نتیجه جمع آن ها.

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

الگوریتم ها چگونگی نوشتن کد را به برنامه نویسان نشان می دهند. به طور معمول یک الگوریتم را می توان به صورت زیر نوشت:

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

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

تجزیه و تحلیل الگوریتم

کارایی یک الگوریتم را می توان در دو مرحله قبل از پیاده سازی و بعد از پیاده سازی تحلیل کرد. که در زیر مشاهده می کنید:

• تجزیه و تحلیل قبل از پیاده سازی (A Priori Analysis): این یک تحلیل نظری از الگوریتم است. کارایی یک الگوریتم با فرض اینکه تمام عوامل تاثیرگذار دیگر (مانند سرعت پردازنده) ثابت هستند، اندازه گیری می شود.
• تجزیه و تحلیل بعدی از پیاده سازی (A Posterior Analysis): این یک تحلیل تجربی از یک الگوریتم است. الگوریتم مورد نظر با استفاده از یک زبان برنامه نویسی پیاده سازی می شود. سپس بر روی کامپیوتر رایانه مقصد اجرا می گردد و در نهایت آمار واقعی مانند زمان و فضای مورد نیاز جمع آوری می شوند.

پیچیدگی الگوریتم

فرض کنید X یک الگوریتم و n اندازه داده های ورودی است، زمان و فضای استفاده شده توسط الگوریتم X دو عامل اصلی هستند که که میزان کارایی الگوریتم X را مشخص می کنند.

• فاکتور زمان : زمان با محاسبه تعداد عملیات کلیدی (مانند عمل مقایسه در الگوریتم مرتب سازی) اندازه گیری می شود.
• فاکتور فضا : فضا با محاسبه حداکثر فضای حافظه مورد نیاز توسط الگوریتم اندازه گیری می شود.

پیچیدگی حافظه

پیچیدگی حافظه یک الگورتیم نشان دهنده مقدار حافظه مورد نیاز الگوریتم در چرخه حیات آن است. حافظه مورد نیاز یک الگوریتم برابر با مجموع دو جزء زیر است:

• یک بخش ثابت که حافظه مورد نیاز برای ذخیره سازی داده و متغیرها می باشد و مستقل از اندازه مسئله است. برای مثال متغیرهای ساده، ثوابت استفاده شده و غیره.
• یک بخش متغیر که حافظه مورد نیاز برای متغیرهای پویا می باشد. این حافظه بسته به اندازه مسئله تغییر می کند. برای مثال تخصیص حافظه پویا، فضای پشته در حالت بازگشتی و غیره.

پیچیدگی حافظه هر الگوریتمی به صورت S(P) = C + S(I) محاسبه می شود که C نشان دهنده بخش ثابت و S(I) هم قسمت متغیر الگوریتم است. مثال زیر را برای درک بهتر موضوع بررسی کنید:

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

در اینجا ما سه متغیر A، B و C و یک ثابت داریم. از این رو S(P) = 1 + 3. حالا میزان حافظه مصرفی به نوع داده متغیرهای داده شده و نوع ثابت بستگی دارد و بر طبق آن محاسبه خواهد شد.

پیچیدگی زمانی

پیچیدگی زمان الگوریتم نشان دهنده مقدار زمانی است که الگوریتم برای تکمیل کار خود نیا دارد. الزامات زمان را می توان به عنوان یک تابع عددی T(n) تعریف کرد. در صورتی که هر محله زمان ثابتی لازم داشته باشد، T(n) می تواند به عنوان تعداد مراحل اندازه گیری شود. برای نمونه، جمع دو عدد صحیح n بیتی، n مرحله لازم دارد. در نتیجه کل زمان محاسباتی به صورت T(n) = c * n محاسبه می شود که c زمانی لازم برای جمع دو بیت است.

نوشته مبانی الگوریتم – آموزش ساختمان داده ها اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.