الگوریتم چیست؟

الگوریتم چیست؟

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

ورودی : الگوریتم میتواند ورودی داشته یا نداشته باشد.

خروجی : الگوریتم باید حداقل یک خروجی داشته باشد.

قطعیت : هر دستور باید واضح و خالی از هر نوع ابهامی باشد.

محدودیت : الگوریتم باید پس از طی مراحل محدودی خاتمه یابد.

کارایی : هر دستور باید انجام پذیر باشد، یعنی بتوان آنرا بصورت دستی و با قلم وکاغذ اجرا کرد.

تفاوت برنامه (Program) و الگوریتم آن است که برنامه لزوما محدود نیست. مثلا سیستم عامل برنامه ای است که دائما در یک سیکل انتظار است تا برنامه بعدی را اجرا کند.

برای ارزیابی کارایی یک الگوریتم، دو مسئله دارای اهمیت است:

1. زمان اجرای الگوریتم

2. حافظه مورد نیاز الگوریتم

از بین این دو عامل زمان اجرا از اهمیت بیشتری برخوردار است. زمان اجرا به عوامل متعددی بستگی دارد از جمله:

سخت افزار : مثلا سرعت پردازنده های مختلف فرق میکند.

کامپایلر : مثلا برنامه های نوشته شده به زبان C معمولا از مشابه پاسکال خود سریعتر هستند.

اندازه ورودی :مثلا در مرتب سازی یک آرایه، هر چه تعداد عناصر آرایه بیشتر باشد، زمان اجرا بیشتر است.

ترکیب یا ترتیب ورودی : در بررسی الگوریتم ها معمولا سه حالت وجود دارد : بهترین حالت (Best case) ، حالت متوسط (Average case) و بدترین حالت (Worst case). مثلا برای مرتب سازی یک آرایه، اگر آرایه از قبل مرتب باشد معمولا بهترین حالت است.

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

اگر n اندازه ورودی باشد، زمان اجرای الگوریتم برحسب n را معمولا با T(n) نشان میدهیم. اگر الگوریتم بیش از یک ورودی داشته باشد که اندازه هایشان مثلا n و m باشد، زمان را با T(n , m) یا T(m , n) نشان میدهیم.

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

برای محاسبه تعداد اجرای جمله اصلی در حلقه های for که اندیس هایشان 1 واحد افزایش می یابد، میتوان از سیگما (∑)  استفاده کرد. به این صورت که به ازای هر حلقه ∑ قرار دهید و جمله داخل حلقه را 1 بگذارید.

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

برای بررسی درستی یک الگوریتم میتوان از Loop invariant(Li) استفاده کرد. باید سه مورد را برسی کنیم:

Initialization : نشان دهیم قبل از اولین اجرای حلقه، نتیجه صحیح است.

Maintenance : اگر قبل از اجرای فعلی حلقه نتیجه درست است، قبل از اجرای بعدی حلقه نیز صحیح بماند.

Termination : وقتی حلقه پایان یافت بتوان نشان داد  که نتیجه دلخواه بدست آمده است.

این مراحل شبیه استقرای ریاضی هستند بجز آخرین مرحله، چون در استقرای معمولی، مقادیر نامحدود هستند و termination ندارد.