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

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

به زبانی ساده، الگوریتم هر روش ساخت یافته ای است که مجموعه ای را به عنوان ورودی میگیرد و مجموعه ای را به عنوان خروجی برمیگرداند! به بیانی دیگر یک سلسله مراتب از عملیاتی که روی داده های ورودی انجام میشود و آنها را به داده های خروجی تبدیل میکند. در این میان همه ی الگوریتم ها "صحیح" نیستند؛ ولذا باید ابتدا به تعریفی برای "الگوریتم های صحیح" بپردازیم.

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

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

احتمالا با این تعاریف، هنوز به پاسخی برای این پرسش که "الگوریتم چیست و چه نوع مسائلی با آن حل میشوند؟" نرسیده اید، لذا در ادامه چند مورد از الگوریتم هایی که در دنیای امروز کاربرد زیادی دارند را بررسی میکنیم تا به شهود بهتری برسیم.

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

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

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

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

دو الگوریتم merge-sort و insertion-sort را در نظر بگیرید، این دو الگوریتم برای مرتب سازی استفاده میشوند و به ازای مجموعه داده هایی که به عنوان ورودی دریافت میکنند، مرتب شده ی این داده ها را به عنوان خروجی برمیگردانند با این تفاوت که اولی در اردر زمانی c1.nlogn نسبت به ورودی و دومی در اردر زمانی c2n^2 نسبت به ورودی کارش را انجام میدهد. فرض کنید به ازای n=10000000 الگوریتم insertion-sort را در کامپیوتری که در هر ثانیه ده بیلیون عملیات انجام میدهد، و الگوریتم merge-sort را در کامپیوتری که در هر ثانیه 10 میلیون عملیات انجام میدهد اجرا کنیم، واضح است که کامپیوتر اول 1000 بار سریعتر از کامپیوتر دوم است. همچنین فرض کنیم ثابت c2 در الگوریتم insertion-sort برابر با 2 باشد و ثابت c1 در الگوریتم merge-sort برابر با 50، با این حساب خواهیم داشت:

میبینیم حتی با وجود این شرایط الگوریتم merge sort در حدود 17 برابر سریعتر از الگوریتم insertion sort است! و این حتی در تعداد ورودی های بالاتر بسیار مشهود تر میشود. برای مثال اگر تعداد 100 میلیون داده ی ورودی برای سورت داشته باشیم، الگوریتم merge-sort در حدود 4 ساعت و الگوریتم insertion-sort در حدود 23 روز زمان برای مرتب سازی آنها زمان نیاز دارند!

نکته ی مورد توجه دیگر این است که مرتبه زمانی اجرای الگوریتم ها نیز به سه مدل best case, average case, worst case تقسیم بندی میشود که البته ما همیشه worst case را گزارش میکنیم، به این دلیل که اولا با این کار یک کران بالا روی زمان اجرایی الگوریتم به ازای هر ورودی دلخواه داریم، دوما در بیشتر الگوریتم ها عمدتا حالت worst case اتفاق میافتد و نهایتا حالت average case نیز تقریبا به بدی حالت worst case است! و لذا معیار ما برای برتری یک الگوریتم بر دیگری همین worst case خواهد بود. برای تحلیل و به دست آوردن زمان اجرای الگوریتم ها روش های مختلفی وجود دارد، یکی از آنها substitution method، دیگری درخت بازگشت ، master theorem و… که در مقاله ی بعدی به بررسی آنها پرداخته خواهد شد.