پیچیدگی محاسباتی کیست؟ توضیح بده.
در علوم کامپیوتر، پیچیدگی رایانشی یا پیچیدگی محاسباتیِ یک الگوریتم مقدار منابع مورد نیاز برای اجرا تا توقف آن است. مهم‌ترین این منابع زمان و حافظه هستند که در ادامه به آنها می‌پردازیم. همچنین پیچیدگی یک مسئله برابر است با پیچیدگی بهترین الگوریتم ممکن برای حل آن مسئله (که شاید هنوز چنین الگوریتمی کشف نشده باشد).به بررسی پیچیدگی یک الگوریتم تحلیل الگوریتم می‌گوییم و مطالعهٔ پیچیدگی یک مسئله را نظریهٔ پیچیدگی محاسباتی می‌نامیم. هر دوی اینها بسیار به یکدیگر مرتبط هستند. اگر برای حل یک مسئله الگوریتمی وجود داشته باشد و پیچیدگی آن را بدانیم، آن پیچیدگی یک کران بالا برای پیچیدگی مسئله است. پیچیدگی از مسائل مهم در طراحی الگوریتم است و برای تحلیل و بررسی میزان کارایی الگوریتم‌ها اهمیت دارد. رفتار مجانبی پیچیدگی بیشترین اهمیت را دارد و معمولاً با نمادهای مجانبی توصیف می‌شود.پیچیدگی یک الگوریتم می‌تواند به عوامل مختلفی وابسته باشد. در پیدا کردن سریع‌ترین مسیر برای یک راننده برای رسیدن از مبدأ به مقصد، هر چه نقشه بزرگتر باشد و خیابان‌ها و کوچه‌ها نیز تودرتوتر و پیچیده‌تر باشند، نیاز به منابع بیشتری برای حل مسئله خواهیم داشت.به طور کلی با بزرگتر شدن ورودی‌های الگوریتم حل مسئله دشوارتر و نیازمند منابع بیشتری است و در نتیجه پیچیدگی را همیشه به صورت تابعی از اندازهٔ ورودی بیان می‌کنیم. به عبارتی دیگر پیچیدگی formula_1 تابعی از عدد طبیعی formula_2 (اندازهٔ ورودی) تعریف می‌شود و یعنی مقدار منابع مورد نیاز برای این که الگوریتم را اجرا کنیم اگر به آن formula_2 ورودی دلخواه بدهیم.در بسیاری از موارد ورودی‌های متفاوت با اندازهٔ یکسان پیچیدگی متفاوتی دارند؛ مثلاً اگر formula_2 را تعداد خیابان‌ها فرض کنیم نوع اتصال خیابان‌ها و ... نیز در میزان منابع مورد نیاز مؤثر اند. به عبارتی دیگر نه تنها تعداد ورودی‌ها، بلکه چیستی ورودی‌ها نیز مؤثر است؛ در حالی که در تحلیل یک الگوریتم، تنها رفتار کلی یک الگوریتم برای ما مهم است (و نه یک حالت خاص). در حقیقت هدف از تعریف پیچیدگی، معیاری برای مقایسهٔ الگوریتم‌ها است و می‌خواهیم بدانیم اگر اندازهٔ ورودی formula_2 باشد چه مقدار منابع نیاز داریم (و نه این که به ما بگویند بستگی دارد). در این موارد بدترین حالت یا میانگین حالات را معیارمان قرار می‌دهیم (بیشینه یا متوسط میان تمام ورودی‌های ممکن به طول formula_2).دلیل اهمیت.کارایی یک برنامه به متغیرهای زیادی وابسته است:همچنین زمان اجرای برنامه حتی به متغیرهای محیطی نیز بستگی دارد. یعنی اگر یک برنامه را چند بار اجرا کنیم زمان اجرای آن ممکن است چند درصد خطا داشته باشد.در این میان پیشرفت در طراحی الگوریتم بیشترین تأثیر را دارد. استفاده از الگوریتمی با پیچیدگی زمانی چندجمله‌ای به جای نمایی تأثیری معادل با هزاران سال پیشرفت در زمینه‌های دیگر دارد.همچنین اگرچه کارایی کامپیوتر بسیار مهم است ولی روی آن کنترل نداریم و هر فردی سخت‌افزار و سیستم عامل ثابتی دارد.منابع رایانشی.زمان.مورد توجه ترین منبع رایانشی زمان است. علم به این که یک الگوریتم در کسری از ثانیه یا چند دقیقه یا چند میلیون سال اجرا می‌شود (سرعت) مهم‌ترین ویژگی آن است. به پیچیدگی زمانی معمولاً به اختصار پیچیدگی می‌گوییم.واحدهای معمول زمان مثل ثانیه و ... در نظریه پیچیدگی استفاده نمی‌شوند زیرا بیش از حد به انتخاب یک کامپیوتر خاص و به تکامل فناوری وابسته هستند. یک کامپیوتر شخصی امروزی می تواند یک الگوریتم را هزاران برابر سریعتر از یک ابررایانه مربوط به ۵۰ سال پیش اجرا کند. در نتیجه زمان یک ویژگی ذاتی الگوریتم نیست، بلکه نتیجه پیشرفت‌های تکنولوژی در سخت‌افزار است.نظریه پیچیدگی محاسباتی به دنبال کمی‌سازی نیازهای منابع زمانی "ذاتی" الگوریتم‌ها است، یعنی محدودیت‌های اساسی که یک الگوریتم روی "هر" کامپیوتری اعمال می‌کند. برای رسیدن به این هدف تعداد "عملیات‌های ابتدایی" (مثل جمع و ضرب و ...) که در طول محاسبه اجرا می شوند را می‌شماریم.حافظه.پیچیدگی حافظه میزان فضایی از حافظهٔ رایانه (مثل RAM) را می‌سنجد که برنامه برای اجرای کامل به آن نیاز دارد.پیچیدگی حافظه در قدیم به دو بخش ثابت و متغیر تقسیم می‌شد:پیچیدگی مسئله.پیچیدگی یک مسئله برابر است با زیرینهٔ پیچیدگی تمام الگوریتم‌های ممکن برای حل آن مسئله (شامل الگوریتم‌هایی که هنوز کشف نشده اند). در نتیجه توصیف یک الگوریتم با نماد formula_7 مسئلهٔ متناظر با آن را نیز توصیف می‌کند. همچنین توصیف یک مسئله با نماد formula_8 تمام الگوریتم‌های حل آن را نیز توصیف می‌کند.برای پیدا کردن مقدار دقیق پیچیدگی یک مسئله (توصیف با نماد formula_9) باید بهینه‌ترین کران بالا و پایین (یکسان) را پیدا کرد. برای پیدا کردن یک کران بالای بهینه باید یک الگوریتم بهینه طراحی کنیم. برای پیدا کردن یک کران پایین بهینه راه کلی وجود ندارد و باید به صورت ریاضی چنین کرانی را اثبات کرد.اگر برای مسئله‌ای کران پایینی اثبات شود و همچنین الگوریتمی با همان پیچیدگی ارائه شود آن الگوریتم را (به صورت مجانبی) بهینه می‌نامیم. به عبارتی دیگر هیچ الگوریتمی (به صورت مجانبی) سریعتر از الگوریتم مذکور وجود ندارد و نخواهد داشت.پیچیدگی مضاعف.همان طور که گفته شد برای حل اکثر مسائل حداقل باید ورودی‌های آن را بخوانیم (و ذخیره کنیم). پیچیدگی مضاعف، میزان منابع مورد نیاز مضاعف بر ورودی گرفتن را می‌سنجد. مثلاً در مرتب‌سازی یک لیست پیوندی به کمک الگوریتم merge sort، حافظه مضاعف مورد نیاز formula_28 است. یعنی به جز خود لیست که ذخیرهٔ آن حافظهٔ formula_29 می‌طلبد، حافظهٔ اضافهٔ دیگری مصرف نمی‌شود.منابع.Jalal Marhon Almaa - Time Travel E-Book