تفاوت میان نسخه‌های «نظریه پیچیدگی محاسباتی»

جز
اصلاح پیوند به صفحه ابهام‌زدایی با استفاده از AWB
(قرار دادن {{داده‌های کتابخانه‌ای}} با اطلاعات ویکی‌داده)
جز (اصلاح پیوند به صفحه ابهام‌زدایی با استفاده از AWB)
بعد از این نظریه که بیان می‌کند کدام مسائل قابل حل و کدام مسائل غیرقابل حل هستند، این سوال به نظر طبیعی می‌رسد که [[درجه سختی]] مساله چقدر است. نظریه پیچیدگی محاسبات در این زمینه‌است.
 
برای سادگی کار مساله‌ها به کلاس‌هایی تقسیم می‌شوند، طوری که مساله‌های یک کلاس از حیث زمان یا فضای مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح [[کلاس‌های پیچیدگی]] خوانده می‌شوند.
 
بعضی منابع دیگری که در این نظریه مورد بررسی قرار می‌گیرند، مثل [[عدم تعین]] صرفاً جنبهٔ آموزشی دارند ولی بررسی آن‌ها موجب درک عمیق‌تر منابع واقعی مثل زمان و فضا می‌شود.
 
معروف‌ترین کلاس‌های پیچیدگی، '''P''' و '''NP''' هستند که مساله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به طور شهودی می‌توان گفت '''P''' کلاس مساله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آن‌ها وجود دارد. اما '''NP''' شامل آن دسته از مساله‌هاست که اگرچه ممکن است پیدا کردن جواب برای آن‌ها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیلهٔ یک [[کارایی الگوریتم‌ها|الگوریتم سریع]] ممکن است.
== [[پیچیدگی زمانی]] ==
 
پیچیدگی زمانی یک مساله تعداد گام‌های مورد نیاز برای حل یک نمونه از یک مساله به عنوان [[تابع|تابعی]] از اندازهٔ ورودی (معمولاً بوسیله تعداد [[بیت (رایانه)|بیت‌ها]] بیان می‌شود) بوسیله کارآمدترین الگوریتم می‌باشد. برای درک بهتر این مساله، فرض کنید که یک مساله با ورودی n بیت در n² گام حل شود. در این مثال می‌گوییم که مساله از درجه پیچیدگی n² می‌باشد. البته تعداد دقیق گام‌ها بستگی به ماشین و زبان مورد استفاده دارد. اما برای صرف نظر کردن از این مشکل، [[نماد O بزرگ]] (Big O notation) معمولاً بکار می‌رود. اگر یک مساله پیچیدگی زمانی از مرتبه (O(n² روی یک کامپیوتر نمونه داشته باشد، معمولاً روی اکثر کامپیوترهای دیگر نیز پیچیدگی زمانی از مرتبه (O(n² خواهدداشت. پس این نشانه به ما کمک می‌کند که صرف نظر از یک کامپیوتر خاص، یک حالت کلی برای پیچیدگی زمانی یک الگوریتم ارائه دهیم.{{سخ}}
پیچیدگی محاسباتی:{{سخ}}
هنگامی که یک الگوریتم خاص را تحلیل می‌کنیم، پیچیدگی زمانی (یا حافظه‌ای) یا مرتبه پیچیدگی زمانی آن را تعیین می‌کنیم. عبارت است از مطالعهٔ تمام الگوریتم‌های امکانپذبر برای حل یک مسئله مفروض است. در تحلیل پیچیدگی محاسباتی کوشش می‌کنیم تا حد پایینی کارایی همه الگوریتم‌ها را برای یک مسئله مفروض به دست آوریم.{{سخ}}
{{علوم رایانه}}
{{داده‌های کتابخانه‌ای}}
 
[[رده:نظریه پیچیدگی محاسباتی]]
[[رده:الگوریتم‌ها]]