موضوع مقاله: پیچیدگی محاسباتی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # پیچیدگی محاسباتی | مقدمه: همچنین پیچیدگی یک مسئله برابر است با پیچیدگی بهترین الگوریتم ممکن برای حل آن مسئله (که شاید هنوز چنین الگوریتمی کشف نشده باشد). | ## بخش 1: پیچیدگی محاسباتی | به بررسی پیچیدگی یک الگوریتم تحلیل الگوریتم می‌گوییم و مطالعهٔ پیچیدگی یک مسئله را نظریهٔ پیچیدگی محاسباتی می‌نامیم. اگر برای حل یک مسئله الگوریتمی وجود داشته باشد و پیچیدگی آن را بدانیم، آن پیچیدگی یک کران بالا برای پیچیدگی مسئله است. پیچیدگی از مسائل مهم در طراحی الگوریتم است و برای تحلیل و بررسی میزان کارایی الگوریتم‌ها اهمیت دارد. رفتار مجانبی پیچیدگی بیشترین اهمیت را دارد و معمولاً با نمادهای مجانبی توصیف می‌شود. در بسیاری از موارد ورودی‌های متفاوت با اندازهٔ یکسان پیچیدگی متفاوتی دارند؛ مثلاً اگر را تعداد خیابان‌ها فرض کنیم نوع اتصال خیابان‌ها و ... به عبارتی دیگر نه تنها تعداد ورودی‌ها، بلکه چیستی ورودی‌ها نیز مؤثر است؛ در حالی که در تحلیل یک الگوریتم، تنها رفتار کلی یک الگوریتم برای ما مهم است (و نه یک حالت خاص). در این موارد بدترین حالت یا میانگین حالات را معیارمان قرار می‌دهیم (بیشینه یا متوسط میان تمام ورودی‌های ممکن به طول ). دلیل اهمیت کارایی یک برنامه به متغیرهای زیادی وابسته است: برنامه در چه دستگاه و سخت‌افزاری اجرا شود و پردازنده و حافظهٔ آن چه قدرتی داشته باشد (کارایی کامپیوتر). یعنی اگر یک برنامه را چند بار اجرا کنیم زمان اجرای آن ممکن است چند درصد خطا داشته باشد. استفاده از الگوریتمی با پیچیدگی زمانی چندجمله‌ای به جای نمایی تأثیری معادل با هزاران سال پیشرفت در زمینه‌های دیگر دارد. | ## بخش 2: پیچیدگی محاسباتی | همچنین اگرچه کارایی کامپیوتر بسیار مهم است ولی روی آن کنترل نداریم و هر فردی سخت‌افزار و سیستم عامل ثابتی دارد. علم به این که یک الگوریتم در کسری از ثانیه یا چند دقیقه یا چند میلیون سال اجرا می‌شود (سرعت) مهم‌ترین ویژگی آن است. در نظریه پیچیدگی استفاده نمی‌شوند زیرا بیش از حد به انتخاب یک کامپیوتر خاص و به تکامل فناوری وابسته هستند. یک کامپیوتر شخصی امروزی می تواند یک الگوریتم را هزاران برابر سریعتر از یک ابررایانه مربوط به ۵۰ سال پیش اجرا کند. در نتیجه زمان یک ویژگی ذاتی الگوریتم نیست، بلکه نتیجه پیشرفت‌های تکنولوژی در سخت‌افزار است. برای رسیدن به این هدف تعداد عملیات‌های ابتدایی (مثل جمع و ضرب و ...) که در طول محاسبه اجرا می شوند را می‌شماریم.بابا محمودی، طلایی پویندگان دانشگاه تحلیل و طراحی الگوریتم‌ها، ۱۱۵–۱۵۰. حافظه پیچیدگی حافظه میزان فضایی از حافظهٔ رایانه (مثل RAM) را می‌سنجد که برنامه برای اجرای کامل به آن نیاز دارد. پیچیدگی حافظه در قدیم به دو بخش ثابت و متغیر تقسیم می‌شد:برگرفته از کتاب ریاضیات گسسته و کاربردهای آن، کنت اچ روزن بخش ثابت فضا معمولاً شامل فضای دستورالعمل، فضای متغیرهای با اندازه ثابت و فضای لازم برای ذخیره ورودی و خروجی‌های برنامه است. بخش متغیر فضا شامل فضای پشته و فضای مورد نیاز برای مقادیر متغیرهایی که اندازه آن‌ها بستگی به مسئله و مشخصات ورودی دارد. پیچیدگی مسئله پیچیدگی یک مسئله برابر است با زیرینهٔ پیچیدگی تمام الگوریتم‌های ممکن برای حل آن مسئله (شامل الگوریتم‌هایی که هنوز کشف نشده اند). | ## بخش 3: پیچیدگی محاسباتی | برای پیدا کردن مقدار دقیق پیچیدگی یک مسئله (توصیف با نماد ) باید بهینه‌ترین کران بالا و پایین (یکسان) را پیدا کرد. برای پیدا کردن یک کران پایین بهینه راه کلی وجود ندارد و باید به صورت ریاضی چنین کرانی را اثبات کرد. برای حل اکثر مسائل حداقل باید ورودی‌های آن را بخوانیم و در نتیجه بیشتر مسائل حداقل خطی هستند. پس از حل مسئله جواب مسئله باید خروجی داده شود و در نتیجه هر مسئله‌ای حداقل به اندازهٔ جوابش پیچیدگی دارد. در بسیاری از مسائل جبر رایانشی مثل حل دستگاه معادلات چندجمله‌ای (غیرخطی) به صورت معادلهٔ مجهولی با درجهٔ ، جواب آنها آن قدر بزرگ می‌شود که چنین کرانی کاربردی می‌شود . برای الگوریتم‌های مرتب‌سازی مقایسه‌ای کران پایین وجود دارد که به کمک درخت تصمیم اثبات می‌شود. اگر برای مسئله‌ای کران پایینی اثبات شود و همچنین الگوریتمی با همان پیچیدگی ارائه شود آن الگوریتم را (به صورت مجانبی) بهینه می‌نامیم. به عبارتی دیگر هیچ الگوریتمی (به صورت مجانبی) سریعتر از الگوریتم مذکور وجود ندارد و نخواهد داشت. پیچیدگی مضاعف همان طور که گفته شد برای حل اکثر مسائل حداقل باید ورودی‌های آن را بخوانیم (و ذخیره کنیم). | ## جمع‌بندی | یعنی به جز خود لیست که ذخیرهٔ آن حافظهٔ می‌طلبد، حافظهٔ اضافهٔ دیگری مصرف نمی‌شود.