پیچیدگی محاسباتی

در علوم کامپیوتر، پیچیدگی رایانشی یا پیچیدگی محاسباتیِ یک الگوریتم مقدار منابع مورد نیاز برای اجرا تا توقف آن است. مهم‌ترین این منابع زمان و حافظه هستند که در ادامه به آنها می‌پردازیم. همچنین پیچیدگی یک مسئله برابر است با پیچیدگی بهترین الگوریتم ممکن برای حل آن مسئله (که شاید هنوز چنین الگوریتمی کشف نشده باشد).

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

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

به طور کلی با بزرگتر شدن ورودی‌های الگوریتم حل مسئله دشوارتر و نیازمند منابع بیشتری است و در نتیجه پیچیدگی را همیشه به صورت تابعی از اندازهٔ ورودی بیان می‌کنیم. به عبارتی دیگر پیچیدگی $f(n)\colon \mathbb {N} \to \mathbb {N}$ تابعی از عدد طبیعی $n$ (اندازهٔ ورودی) تعریف می‌شود و یعنی مقدار منابع مورد نیاز برای این که الگوریتم را اجرا کنیم اگر به آن $n$ ورودی دلخواه بدهیم.

در بسیاری از موارد ورودی‌های متفاوت با اندازهٔ یکسان پیچیدگی متفاوتی دارند؛ مثلاً اگر $n$ را تعداد خیابان‌ها فرض کنیم نوع اتصال خیابان‌ها و ... نیز در میزان منابع مورد نیاز مؤثر اند. به عبارتی دیگر نه تنها تعداد ورودی‌ها، بلکه چیستی ورودی‌ها نیز مؤثر است؛ در حالی که در تحلیل یک الگوریتم، تنها رفتار کلی یک الگوریتم برای ما مهم است (و نه یک حالت خاص). در حقیقت هدف از تعریف پیچیدگی، معیاری برای مقایسهٔ الگوریتم‌ها است و می‌خواهیم بدانیم اگر اندازهٔ ورودی $n$ باشد چه مقدار منابع نیاز داریم (و نه این که به ما بگویند بستگی دارد). در این موارد بدترین حالت یا میانگین حالات را معیارمان قرار می‌دهیم (بیشینه یا متوسط میان تمام ورودی‌های ممکن به طول $n$).

دلیل اهمیت

کارایی یک برنامه به متغیرهای زیادی وابسته است:

• برنامه در چه دستگاه و سخت‌افزاری اجرا شود و پردازنده و حافظهٔ آن چه قدرتی داشته باشد (کارایی کامپیوتر).
• برنامه در چه سیستم عاملی اجرا شود.
• برنامه در چه زبانی نوشته شود.
• برای کامپایل برنامه از چه کامپایلری استفاده شود (بهینگی کامپایلر).
• از چه الگوریتمی و با چه اندازهٔ ورودی استفاده شود (کارایی الگوریتم).

همچنین زمان اجرای برنامه حتی به متغیرهای محیطی نیز بستگی دارد. یعنی اگر یک برنامه را چند بار اجرا کنیم زمان اجرای آن ممکن است چند درصد خطا داشته باشد.

در این میان پیشرفت در طراحی الگوریتم بیشترین تأثیر را دارد. استفاده از الگوریتمی با پیچیدگی زمانی چندجمله‌ای به جای نمایی تأثیری معادل با هزاران سال پیشرفت در زمینه‌های دیگر دارد.

همچنین اگرچه کارایی کامپیوتر بسیار مهم است ولی روی آن کنترل نداریم و هر فردی سخت‌افزار و سیستم عامل ثابتی دارد.

منابع رایانشی

زمان

مقالهٔ اصلی: پیچیدگی زمانی

مورد توجه ترین منبع رایانشی زمان است. علم به این که یک الگوریتم در کسری از ثانیه یا چند دقیقه یا چند میلیون سال اجرا می‌شود (سرعت) مهم‌ترین ویژگی آن است. به پیچیدگی زمانی معمولاً به اختصار پیچیدگی می‌گوییم.

واحدهای معمول زمان مثل ثانیه و ... در نظریه پیچیدگی استفاده نمی‌شوند زیرا بیش از حد به انتخاب یک کامپیوتر خاص و به تکامل فناوری وابسته هستند. یک کامپیوتر شخصی امروزی می تواند یک الگوریتم را هزاران برابر سریعتر از یک ابررایانه مربوط به ۵۰ سال پیش اجرا کند. در نتیجه زمان یک ویژگی ذاتی الگوریتم نیست، بلکه نتیجه پیشرفت‌های تکنولوژی در سخت‌افزار است.

نظریه پیچیدگی محاسباتی به دنبال کمی‌سازی نیازهای منابع زمانی ذاتی الگوریتم‌ها است، یعنی محدودیت‌های اساسی که یک الگوریتم روی هر کامپیوتری اعمال می‌کند. برای رسیدن به این هدف تعداد عملیات‌های ابتدایی (مثل جمع و ضرب و ...) که در طول محاسبه اجرا می شوند را می‌شماریم.

حافظه

پیچیدگی حافظه میزان فضایی از حافظهٔ رایانه (مثل RAM) را می‌سنجد که برنامه برای اجرای کامل به آن نیاز دارد.

پیچیدگی حافظه در قدیم به دو بخش ثابت و متغیر تقسیم می‌شد:

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

پیچیدگی مسئله

پیچیدگی یک مسئله برابر است با زیرینهٔ پیچیدگی تمام الگوریتم‌های ممکن برای حل آن مسئله (شامل الگوریتم‌هایی که هنوز کشف نشده اند). در نتیجه توصیف یک الگوریتم با نماد ${\mathcal {O}}$ مسئلهٔ متناظر با آن را نیز توصیف می‌کند. همچنین توصیف یک مسئله با نماد $\Omega$ تمام الگوریتم‌های حل آن را نیز توصیف می‌کند.

برای پیدا کردن مقدار دقیق پیچیدگی یک مسئله (توصیف با نماد $\Theta$) باید بهینه‌ترین کران بالا و پایین (یکسان) را پیدا کرد. برای پیدا کردن یک کران بالای بهینه باید یک الگوریتم بهینه طراحی کنیم. برای پیدا کردن یک کران پایین بهینه راه کلی وجود ندارد و باید به صورت ریاضی چنین کرانی را اثبات کرد.

• برای حل اکثر مسائل حداقل باید ورودی‌های آن را بخوانیم و در نتیجه بیشتر مسائل حداقل خطی $\Omega (n)$ هستند.
• پس از حل مسئله جواب مسئله باید خروجی داده شود و در نتیجه هر مسئله‌ای حداقل به اندازهٔ جوابش پیچیدگی دارد. در بسیاری از مسائل جبر رایانشی مثل حل دستگاه معادلات چندجمله‌ای (غیرخطی) به صورت $n$ معادلهٔ $n$ مجهولی با درجهٔ $d$، جواب آنها آن قدر بزرگ می‌شود ($d^{n}$) که چنین کرانی کاربردی می‌شود $\Omega (d^{n})$.
• یک روش معمول برای اثبات یک کران پایین کاهش مسئله است. فرض کنید اگر مسئلهٔ $A$ با ${\mathcal {O}}(g)$ حل شود، مسئلهٔ $B$ را بتوان به کمک حل مسئلهٔ $A$ با ${\mathcal {O}}(f(g))$ حل کرد. حال اگر مسئلهٔ $B$ از $\Omega (h)$ باشد، مسئلهٔ $A$ حتماً از $\Omega (f^{-1}(h))$ است. در اینجا از کاهش مسئلهٔ $A$ به مسئلهٔ $B$ استفاده کردیم. این تکنیک برای اثبات کران پایین در مسائل NP-complete کاربرد بسیاری دارد.
• برای الگوریتم‌های مرتب‌سازی مقایسه‌ای کران پایین $\Omega (n\lg n)$ وجود دارد که به کمک درخت تصمیم اثبات می‌شود. در نتیجه الگوریتم‌هایی مثل quick sort و merge sort بهینه هستند.

اگر برای مسئله‌ای کران پایینی اثبات شود و همچنین الگوریتمی با همان پیچیدگی ارائه شود آن الگوریتم را (به صورت مجانبی) بهینه (به انگلیسی: asymptotically optimal) می‌نامیم. به عبارتی دیگر هیچ الگوریتمی (به صورت مجانبی) سریعتر از الگوریتم مذکور وجود ندارد و نخواهد داشت.

پیچیدگی مضاعف

همان طور که گفته شد برای حل اکثر مسائل حداقل باید ورودی‌های آن را بخوانیم (و ذخیره کنیم). پیچیدگی مضاعف، میزان منابع مورد نیاز مضاعف بر ورودی گرفتن را می‌سنجد. مثلاً در مرتب‌سازی یک لیست پیوندی به کمک الگوریتم merge sort، حافظه مضاعف مورد نیاز ${\mathcal {O}}(1)$ است. یعنی به جز خود لیست که ذخیرهٔ آن حافظهٔ ${\mathcal {O}}(n)$ می‌طلبد، حافظهٔ اضافهٔ دیگری مصرف نمی‌شود.

جستارهای وابسته

• نمادهای مجانبی
• نظریه پیچیدگی محاسباتی
• طراحی الگوریتم
• مهندسی الگوریتم

منابع

Jalal Marhon Almaa - Time Travel E-Book