تحلیل الگوریتم | تحلیل مجانبی | راهنمای کاربردی

۲۲ اردیبهشت ۱۴۰۰ توسط الهام حصارکی مجموعه: مهندسی کامپیوتر

در این مطلب به بحث تحلیل الگوریتم و به طور خاص تحلیل مجانبی الگوریتم پرداخته شده است. 

چرا تحلیل کارایی الگوریتم حائز اهمیت است؟

ویژگی‌های مهمی وجود دارد که باید پیرامون یک الگوریتم مد نظر داشت. از جمله این ویژگی‌ها می‌توان به کاربرپسندی، دانه‌بندی (ماژولاریتی)، امنیت، قابلیت نگهداری و دیگر موارد اشاره کرد. اما پرسشی که در این وهله مطرح می‌شود این است که چرا باید نگران کارایی الگوریتم‌ها بود.

پاسخ این پرسش ساده است. همه ویژگی‌های بیان شده در بالا را تنها در صورتی می‌توان داشت که الگوریتم کارایی (Performance) داشته باشد. بنابراین، کارایی مانند ارزی است که با استفاده از آن می‌توان همه ویژگی‌های بیان شده در بالا برای یک الگوریتم را خرید. دلیل دیگر برای مطالعه پیرامون کارایی این است که سرعت اجرای یک الگوریتم مسئله بسیار مهم و قابل توجهی است و ارتباط تنگاتنگی بین سرعت یک الگورتیم و کارایی آن وجود دارد.

در مجموع، باید گفت که کارایی==مقیاس است. برای درک بهتر مطالب بیان شده، ویرایشگر متنی مفروض است که می‌تواند ۱۰۰۰ صفحه را بارگذاری کند، اما غلط‌یابی آن یک صفحه در هر دقیقه است. به عنوان مثالی دیگر، ویرایشگر متنی مفروض است که در آن چرخاندن یک عکس به صورت ۹۰ درجه ۱ ساعت زمان می‌برد. مشخص است که چنین سرعت اجرایی عملا کاربری نرم‌افزار را از میان می‌برد و در واقع، آن را فاقد کارایی می‌کند. شایان توجه است که به علاقه‌مندان برای مطالعه بیشتر پیرامون تحلیل و طراحی الگوریتم‌ها، مطالعه مطلب «درس الگوریتم های پیشرفته | مفاهیم پایه به زبان ساده» پیشنهاد می‌شود. همچنین، برای مطالعه جامع و کامل پیرامون مرتبه زمانی، مطالعه مطلب «پیچیدگی زمانی الگوریتم های مرتب سازی با نماد O بزرگ — به زبان ساده» پیشنهاد می‌شود.

چطور از بین دو الگوریتم با عملکرد یکسان، بهترین انتخاب می‌شود؟

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

  • ممکن است این امکان وجود داشته باشد که برای برخی از ورودی‌ها، اولین الگوریتم بهتر از دومین مورد کار کند. در حالی که امکان دارد برای برخی دیگر از ورودی‌ها، دومین الگوریتم عملکرد بهتری داشته باشد.
  • این امکان برای برخی از ورودی‌ها وجود دارد که الگوریتم اول روی برخی از دستگاه‌ها و الگوریتم دوم روی برخی از دیگر دستگاه‌ها عملکرد بهتری داشته باشد.

تحلیل مجانبی (Asymptotic Analysis) ایده بزرگی است که دو مسئله بیان شده در بالا ضمن تحلیل کارایی الگوریتم‌ها را مدیریت می‌کند. در تحلیل مجانبی، کارایی یک الگوریتم بر اساس اندازه ورودی سنجیده می‌شود و زمان اجرای واقعی سنجیده نمی‌شود. در واقع، سنجیده می‌شود که زمان (یا فضا) مصرفی یک الگوریتم چگونه با افزایش اندازه ورودی آن تغییر می‌کند.

برای مثال، مسئله جستجو مفروض است. در این مسئله تعدادی داده به عنوان ورودی به الگوریتم داده می‌شود و الگوریتم وظیفه مرتب کردن این داده‌ها را دارد. یک راهکار برای انجام این کار استفاده از جستجوی خطی (Linear Search) است. مرتبه رشد الگوریتم جستجوی خطی، «خطی» است. راهکار دیگر برای مرتب‌سازی ورودی‌ها استفاده از جستجوی دودویی (Binary Search) است که مرتبه رشد آن لگاریتمی است.

برای درک بهتر آنکه تحلیل مجانبی چگونه مسائل بیان شده در بالا را در تحلیل الگوریتم‌ها حل می‌کند، فرض می‌شود که کاربر الگوریتم جستجوی خطی را روی کامپیوتر سریع A و الگوریتم جستجوی دودویی را روی کامپیوتر کند B اجرا کرده و ورودی‌های یکسانی را به هر دو الگوریتم می‌دهد تا سرعت اجرا و ارائه خروجی آن‌ها را بسنجد. همچنین، یک مقدار ثابت نیز وجود دارد که مشخص می‌کند سرعت کامپیوتر A چقدر از کامپیوتر B بیشتر است. اگر این ثابت برای کامپیوتر A برابر با ۰٫۲ و برای کامپیوتر B برابر با ۱۰۰۰ باشد، بدین معنا است که کامپیوتر A به میزان ۵۰۰۰ بار قدرتمندتر از کامپیوتر B است.

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

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

  • زمان اجرای جستجوی خطی (به ثانیه) در کامپیوتر A برابر است با: n * ۰٫۲
  • زمان اجرای جستجوی دودویی (به ثانیه) در کامپیوتر B برابر است با: ۱۰۰۰ * log (n)

چطور از بین دو الگوریتم با عملکرد یکسان، بهترین انتخاب می‌شود؟

آیا تحلیل مجانبی عملکرد همیشه کارا است؟

تحلیل مجانبی عالی نیست، اما بهترین راهکار موجود برای تحلیل الگوریتم‌ها است. برای مثال، فرض می‌شود که دو نوع الگوریتم مرتب‌سازی وجود دارد که به ترتیب زمانی برابر با ۱۰۰۰nLogn و ۲nLogn دارند. هر دو این الگوریتم‌ها به طور مجانبی مشابه هستند (مرتبه رشد nLogn است).

بنابراین، با تحلیل مجانبی، نمی‌توان قضاوت کرد که کدام یک از این دو الگوریتم بهتر است زیرا در تحلیل مجانبی مقدار ثابت در نظر گرفته نمی‌شود. همچنین، در تجلیل مجانبی همواره پیرامون اندازه داده‌ای بزرگ‌تر از مقدار ثابت صحبت می‌شود.

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

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

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

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

آموزش طراحی الگوریتم

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

آموزش طراحی الگوریتم به همراه حل مثال های عملی

این ویدئوی آموزشی توسط «مهندس مهدی اشرفی» تدریس شده و طول مدت آن هشت ساعت و شانزده دقیقه است. در این آموزش، ابتدا به آشنایی با طراحی الگوریتم پرداخته شده و سپس، مباحث روش‌های بازگشتی، روش‌های تقسیم و حل، روش حریصانه و روش برنامه‌نویسی پویا مورد بررسی قرار گرفته‌اند.

آموزش طراحی الگوریتم (مرور – تست کنکور ارشد)‎

این ویدئوی آموزشی توسط «مهندس مهدی اشرفی» تدریس شده و طول مدت آن چهارده ساعت و چهل و هفت دقیقه است. رویکرد این آموزش مروری و با حل تست‌های کنکور ارشد برای مباحث مرتبه اجرایی، روش بازگشتی، روش تقسیم و حل، روش پویا، روش حریصانه، روش عقب‌گرد، الگوریتم‌های گراف و مسائل پی و ان‌پی (مسائل P و مسائل NP) است.

آموزش مروری بر پیچیدگی محاسبات (Computational Complexity)

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

آموزش الگوریتم موازی و پردازش موازی

این ویدئوی آموزشی توسط «مهندس منوچهر بابایی» تدریس شده و طول مدت آن سیزده ساعت و دو دقیقه است. در این دوره، ضمن بیان مقدمه‌ای پیرامون پردازش موازی و تحلیل الگوریتم‌ها، مباحث مسئله انتخاب، ادغام، مرتب‌سازی، جستجو و عملیات ماتریسی مورد بررسی قرار می‌گیرند.

آموزش رابطه‌های بازگشتی در طراحی الگوریتم و ساختمان گسسته (مرور – تست کنکور ارشد)

این ویدئوی آموزشی توسط «مهندس فرشید شیرافکن» تدریس شده و طول مدت آن یک ساعت و پنجاه و چهار دقیقه است. رویکرد این آموزش مروری و با حل تست‌های کنکور ارشد برای مبحث رابطه‌های بازگشتی است.

آموزش روش تقسیم و حل در طراحی الگوریتم (مرور – تست کنکور کارشناسی ارشد)

این ویدئوی آموزشی توسط «مهندس فرشید شیرافکن» تدریس شده و طول مدت آن یک ساعت و پنجاه دقیقه است. رویکرد این آموزش مروری و با حل تست‌های کنکور ارشد برای مباحث روش تقسیم و حل است.

آموزش نرم‌افزار Raptor برای ترسیم فلوچارت

این ویدئوی آموزشی توسط «مهندس محمد جباری» تدریس شده و طول مدت آن پنجاه و سه دقیقه است. در این آموزشی چگونگی کار با نرم‌افزار Raptor و ترسیم فلوچارت با استفاده از آن مورد بررسی قرار گرفته است.

منابع آموزشی ساختمان داده ها

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

اگر این مطلب برای شما مفید بوده است، آموزش‌ها و مطالب زیر نیز به شما پیشنهاد می‌شوند:

 

منبع [+]

مجموعه: مهندسی کامپیوتر برچسب ها: , , , , , , , , , ,
یک نظر در "تحلیل الگوریتم | تحلیل مجانبی | راهنمای کاربردی"

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *