شاید لازم نباشه که شما رو قانع کنم الگوریتم‌ها چقدر مهم هستن، اگه بدونید مصاحبه‌های شغلی برنامه‌نویسی معمولاً چطوری طراحی می‌شن واحتمالاً خودتون می‌دونید که سوالاتی که تو این مصاحبه‌ها می‌پرسن معمولاً مربوط به ساختار داده‌ها (Data Structures) و الگوریتم‌ها (Algorithms) هستن.
هدفمون اینه که یه درک شهودی از اینکه الگوریتم‌ها چی هستن بهتون بدیم. چرا باید اون‌ها رو مطالعه کنیم و چرا شرکت‌ها اینقدر به الگوریتم‌ها اهمیت میدن که کل فرآیند استخدامشون رو حول بررسی این موضوعات طراحی می‌کنن.
الگوریتم چیه؟
الگوریتم یه سری قدمه (series of steps) که برای انجام یه کار یا رسیدن به یه هدف طراحی شده.
ما یه ورودی(input) داریم، یعنی یه سری داده(data) که می‌خوایم کاری روش انجام بدیم. و باید بفهمیم چه مراحل منطقی‌ای (logical steps) نیاز داریم که به کامپیوتر بگیم انجام بده، تا به خروجی (output) مطلوبمون برسیم.
مطالعه الگوریتم‌های کامپیوتری دقیقاً درباره استفاده از منابع کامپیوتر برای حل عملیات یا مسائل ریاضیه. ما می‌خوایم به جای استفاده از مغز انسان، این مسائل رو با کمک کامپیوتر حل کنیم. و مزیت کامپیوتر اینه که می‌تونه این عملیات رو با سرعت فوق‌العاده بالا انجام بده.
سوال یک میلیون دلاری
اگر کامپیوترها اینقدر سریع هستن، چرا اصلاً مهمه که چه الگوریتمی طراحی کنیم؟ چرا اینقدر به سرعت الگوریتم‌ها اهمیت می‌دیم؟
مسئله‌های پیشرفته حوزه علوم کامپیوتر، مسائلی هستن که اندازه ورودی‌شون واقعاً بزرگه.
وقتی به شرکت‌هایی مثل گوگل (Google) و فیسبوک (Facebook) فکر می‌کنید، سایز داده‌هایی که این الگوریتم‌ها باهاش کار می‌کنن، ۱۰۰ یا ۱۰۰۰ آیتم نیست؛ می‌تونه میلیاردها و میلیاردها و میلیاردها آیتم باشه.
الگوریتم‌ها چطور اهمیت پیدا می‌کنن؟
تو این مقیاس‌ها حتی با قدرت کامپیوترهایی که امروز داریم، طراحی الگوریتم شما، یعنی سرعتش و مقدار حافظه‌ای که مصرف می‌کنه، واقعاً اهمیت زیادی پیدا می‌کنه.
پس با طراحی الگوریتم‌های سریع‌تر مثل پیج رنک میتونیم، اولاً مسائل خیلی بزرگ‌تری رو حل کنیم و دوماً میتونیم عملکرد فناوری‌مون رو به اندازه یک دهه پیشرفت در سرعت پردازش کامپیوترها بهبود بدیم.
پس به طور کلی در مورد الگوریتم‌ها، چیزهایی که برامون مهمه، سرعت اجراش و حافظه‌ای که استفاده می‌کنه هست.
چیزهایی که برای ما مهمه، سرعتی که اجرا می‌شن و حافظه‌ای که مصرف می‌کنن.
در سطح خیلی خیلی پایه‌ای، میتونیم سرعت الگوریتم رو فقط به عنوان تعداد دستوراتی(instructions) که باید اجرا کنه برای تکمیل کار در نظر بگیریم.
حالا بیایید یه الگوریتم خیلی پایه‌ای رو بررسی کنیم:
فرض کنید یه کتاب دارید و می‌خواید یه صفحه خاص رو توش پیدا کنید.
فرض کنید می‌خواهید به کسی بگید که صفحه ۱۰۰ رو توی کتاب پیدا کنه. چطور می‌خواید این کار رو انجام بدید؟
یکی از روش‌های خیلی ساده (naive) می‌تونه این باشه که شروع کنید به باز کردن صفحه‌ها یکی یکی و بررسی کنید:
- صفحه ۱ رو باز کنید.
- ببینید آیا صفحه ۱۰۰ هست یا نه.
- اگه بله، پیداش کردید و کار تمومه.
- اگه نه، صفحه بعدی رو باز کنید و همین کار رو تکرار کنید.
ممکنه این روش یه کم احمقانه به نظر برسه، ولی واقعاً اگه این کار رو 100 بار انجام بدید، در نهایت به صفحه 100 می‌رسید.
این الگوریتم واقعاً کار می‌کنه ولی چه مشکلی داره؟
خیلی کنده (slow) درسته؟ و احتمالاً روش خیلی بهتری برای انجام این کار وجود داره.
ایده بهبود الگوریتم:
شما ممکنه بگید که در این مورد خاص، زمان اجرای الگوریتم ما 100 دور تکرار یا 100 دستور بوده.
اما گفتن اینکه این الگوریتم زمان اجرایی (running time) 100 دستور داره، خیلی مفید نیست چون در این مورد ما می‌خواهیم صفحه 100 رو پیدا کنیم.
اگه بهتون می‌گفتم که صفحه دو رو پیدا کنید چی؟
در این صورت، شما صفحه یک رو باز می‌کردید و می‌گفتید: “آیا این صفحه دو هست؟” نه؟ برید سراغ صفحه بعدی.
آیا این صفحه دو هست؟ بله، ما جواب رو پیدا کردیم.
در این حالت، زمان اجرا (running time) تنها دو خواهد بود.
ولی ممکنه به بدترین حالت فکر کنید، وقتی به شما می‌گم که باید صفحه آخر کتاب رو پیدا کنید.
این کتاب ۶۹۶ صفحه داره. ولی در این حالت باید ۶۹۶ بار تکرار (iterations) انجام بدیم تا شماره صفحه رو پیدا کنیم.
چطور میتونیم این ایده از زمان اجرا رو در این الگوریتم خاص تعمیم بدیم؟
برای متخصصان، ما وقتی الگوریتم‌ها رو تحلیل می‌کنیم، در واقع خیلی بدبین هستیم.
اول از همه همیشه به بدترین حالت ممکن فکر می‌کنیم. ما فرض می‌کنیم که بدترین حالت ممکن برای ما پیش میاد و همیشه بدترین حالت ممکن رو داریم.
به همین دلیل، در علم کامپیوتر وقتی الگوریتم‌ها رو تحلیل می‌کنیم می‌گیم که زمان اجرای Big O یا همون زمان اجرای بدترین حالت، 696 است.
ولی اگه کتاب دیگه‌ای داشتیم، چی؟
فرض کنید این کتاب بیوگرافی لئوناردو داوینچی باشه که ۵۹۹ صفحه داره.
در این حالت، همین الگوریتم زمان اجراش به‌عنوان Big O برابر با 599 خواهد بود.
اما این هم خیلی مفید نیست، چون حالا حتی با اینکه تا حدودی زمان اجرا رو از نظر بدترین حالت تعمیم دادیم، زمان اجرای ما هنوز به خود کتاب بستگی داره.
پس چطور میتونیم زمان اجرای این الگوریتم جستجوی خاص، که بهش جستجوی خطی (Linear Search) می‌گیم، رو برای هر مسئله و هر کتابی تعمیم بدیم؟
راهی که توی علم کامپیوتر به این موضوع نگاه می‌کنیم، از نظر اندازه ورودی (Input Size) هست. یعنی برای هر صفحه‌ای که به کتاب اضافه می‌کنیم، زمان اجرای الگوریتم ما یکی افزایش پیدا می‌کنه.
پس به زبان علم کامپیوتر، الگوریتم ما زمان اجرای خطی داره یا به عبارت دیگه، زمان اجرای الگوریتم برابر با O(n) است که در اون n اندازه مسئله رو نشون می‌ده.
جستجوی دودویی (Binary Search)
چطور میتونیم الگوریتمی پیدا کنیم که شاید خیلی سریع‌تر از باز کردن صفحه‌ها یکی‌یکی باشه؟
احتمالاً به طور شهودی فکر می‌کنید که مطمئناً منطقی نیست حتی از صفحه‌های اول شروع کنید، چون می‌دونید که صفحه مورد نظر توی صفحه اول نیست، درسته؟
- میتونیم به کامپیوتر بگیم که مثلاً توی اولین دور تکرار، همیشه صفحه وسط رو امتحان کنه و از وسط کتاب بازش کنه.
- بعدش میتونیم خیلی سریع با استفاده از یه دستور بررسی کنیم که آیا صفحه‌ای که دنبالش می‌گردیم قبل از صفحه‌ای که باز کردیم هست یا بعد از اون.
- اگه مثلا صفحه مورد نظر ما نیمه چپ کتاب باشه به کامپیوتر بگیم که حالا صفحه وسط نیمه چپ کتاب رو باز کنه.
- اینطوری میتونیم دوباره کل بقیه کتاب رو کنار بذاریم و فقط روی نیمی از نیمه چپ تمرکز کنیم.
- و دوباره وسط این قسمت از کتاب رو باز کنیم
در نهایت با این فرایند تکراری، ما خیلی سریع‌تر به جواب خواهیم رسید.
زمان اجرای این روش O(log n) است، یعنی با افزایش تعداد صفحات، زمان لازم برای جستجو فقط کمی بیشتر می‌شه و خیلی سریع‌تر از روش خطی است.
حالا تصور کنید که بخواهیم یه داده خاص رو از لیستی مثل میلیاردها و میلیاردها و میلیاردها داده پیدا کنیم این الگوریتم زمان اجرا رو می‌تونه به اندازه هفته‌ها یا حتی ماه‌ها کوتاه‌تر کنه!
امیدوارم حالا یه مقدار متوجه شده باشید که چرا شرکت‌ها اینقدر به استخدام افرادی که الگوریتم‌ها رو می‌فهمند و می‌دونند چطور الگوریتم‌های خوب برای مسائل خیلی بزرگ خودشون بنویسند، اهمیت میدن.