پیچیدگی و تحلیل الگوریتمها
تحلیل الگوریتمها چگونگی رشد زمان اجرا و حافظه مورد نیاز یک الگوریتم را با افزایش اندازه ورودی کمیسازی میکند و واژگان و ابزارهای مجانبی را برای مقایسه الگوریتمها و شناسایی مسائل ذاتاً دشوار فراهم میآورد.
Definition
تحلیل الگوریتمها مطالعه منابع محاسباتی — عمدتاً زمان و فضا — است که یک الگوریتم به عنوان تابعی از اندازه ورودی خود مصرف میکند، همراه با تکنیکهایی که برای استخراج، بیان و مقایسه این محدودیتهای منابع استفاده میشود.
Scope
این حوزه شامل اندازهگیری و مقایسه مصرف منابع الگوریتمی است: نمادگذاری مجانبی (O بزرگ، امگا بزرگ، تتا بزرگ)، حل روابط بازگشتی ناشی از الگوریتمهای بازگشتی، تحلیل استهلاکی توالی عملیات، و مبانی کلاسهای پیچیدگی محاسباتی و NP-کامل بودن در طراحی الگوریتم. این حوزه به هزینه بدترین حالت، حالت متوسط و استهلاکی، و تمایز بین مسائل قابل حل و غیرقابل حل میپردازد. نظریه گستردهتر محاسبات (محاسبهپذیری، کلاسهای پیچیدگی رسمی) به یک زیرشاخه جداگانه تعلق دارد؛ در اینجا تمرکز بر تحلیل الگوریتمهای مشخص است.
Sub-topics
Core questions
- چگونه مصرف منابع یک الگوریتم مستقل از جزئیات ماشین و پیادهسازی بیان میشود؟
- تحلیل بدترین حالت، حالت متوسط و استهلاکی هر کدام چه اطلاعاتی به ما میدهند؟
- روابط بازگشتی تولید شده توسط الگوریتمهای بازگشتی چگونه برای محدودیتهای مجانبی حل میشوند؟
- چگونه میتوان محدودیتهای پایین را تعیین کرد که نشان دهد هیچ الگوریتمی نمیتواند بهتر عمل کند؟
- NP-کامل بودن یک مسئله به چه معناست و چرا برای طراحی اهمیت دارد؟
Key concepts
- O بزرگ، امگا بزرگ، تتا بزرگ
- تحلیل بدترین حالت و حالت متوسط
- روابط بازگشتی
- قضیه اصلی
- تحلیل استهلاکی
- محدودیتهای پایین
- زمان چندجملهای
- NP-کامل بودن
Key theories
- نمادگذاری مجانبی
- O بزرگ، امگا بزرگ و تتا بزرگ نرخ رشد مصرف منابع را با افزایش اندازه ورودی توصیف میکنند و با انتزاع ثابتها و جملات مرتبه پایینتر، امکان مقایسه الگوریتمها را مستقل از ماشین فراهم میآورند.
- قابلیت حل و NP-کامل بودن
- مسائلی که در زمان چندجملهای قابل حل هستند، قابل حل در نظر گرفته میشوند؛ مسائل NP-کامل مسائلی هستند که تمام مسائل در NP به آنها کاهش مییابند، و یافتن یک الگوریتم چندجملهای برای هر یک، همه آنها را حل خواهد کرد، سؤالی (P در مقابل NP) که همچنان باز است.
Clinical relevance
تحلیل الگوریتمها هر تصمیم مهندسی را در مورد اینکه از کدام الگوریتم یا ساختار داده استفاده شود، هدایت میکند و پیشبینی میکند که سیستمها با رشد دادهها چگونه مقیاسپذیر خواهند بود. تشخیص اینکه یک مسئله NP-سخت است، به متخصصان میگوید که به جای یک الگوریتم دقیق چندجملهای، به دنبال روشهای تقریبی، اکتشافی یا موارد خاص باشند، که کار را در بهینهسازی، زمانبندی و محاسبات در مقیاس بزرگ شکل میدهد.
History
نمادگذاری مجانبی از نظریه تحلیلی اعداد وارد علوم کامپیوتر شد و توسط دونالد کنوت در دهههای ۱۹۶۰ و ۱۹۷۰ رایج گشت. نظریه NP-کامل بودن توسط استفان کوک (۱۹۷۱) پایهگذاری شد و توسط ریچارد کارپ (۱۹۷۲) گسترش یافت، که طراحی الگوریتم را حول مرز بین مسائل قابل حل و غیرقابل حل بازتعریف کرد.
Debates
- P در مقابل NP
- اینکه آیا هر مسئلهای که راهحلهای آن را میتوان به سرعت تأیید کرد، میتواند به سرعت نیز حل شود (P = NP)، سؤال اصلی و باز علوم کامپیوتر نظری است؛ به طور گستردهای گمان میرود که P برابر NP نیست، اما هیچ اثباتی وجود ندارد.
Key figures
- Donald Knuth
- Stephen Cook
- Richard Karp
- Robert Tarjan
Related topics
Seminal works
- cormen2009
- knuth1976bigo
- kleinberg2006
Frequently asked questions
- تفاوت بین تحلیل بدترین حالت و حالت متوسط چیست؟
- تحلیل بدترین حالت، مصرف منابع را برای نامطلوبترین ورودی از هر اندازه محدود میکند و یک تضمین ارائه میدهد. تحلیل حالت متوسط، مصرف منابع مورد انتظار را در یک توزیع از ورودیها تخمین میزند، که میتواند نمایندهتر از عملکرد معمول باشد اما به مفروضاتی در مورد توزیع ورودی بستگی دارد.
- اگر یک مسئله NP-کامل باشد، آیا حل آن ناامیدکننده است؟
- خیر. NP-کامل بودن به این معنی است که هیچ الگوریتم کارآمدی برای بدترین حالت شناخته شده نیست، اما اغلب میتوان نمونهها را با الگوریتمهای تقریبی، اکتشافی، الگوریتمهای نمایی که در عمل به اندازه کافی سریع هستند، یا با بهرهبرداری از ساختار خاص حل کرد. این نشاندهنده تغییر استراتژی است، نه غیرممکن بودن.