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

جز (ربات: مرتب‌سازی رده‌ها؛ زیباسازی)
== [[پیچیدگی زمانی]] ==
 
پیچیدگی زمانی یک مساله تعداد گام‌های مورد نیاز برای حل یک نمونه از یک مساله به عنوان [[تابع|تابعی]] از اندازهٔ ورودی (معمولاً بوسیله تعداد [[بیت|بیت‌ها]] بیان می‌شود) بوسیله کارآمدترین الگوریتم می‌باشد. برای درک بهتر این مساله، فرض کنید که یک مساله با ورودی n بیت در n² گام حل شود. در این مثال می‌گوییم که مساله از درجه پیچیدگی n² می‌باشد. البته تعداد دقیق گام‌ها بستگی به ماشین و زبان مورد استفاده دارد. اما برای صرف نظر کردن از این مشکل، [[نماد O بزرگ]] (Big O notation) معمولاً بکار می‌رود. اگر یک مساله پیچیدگی زمانی از مرتبه (O(n² روی یک کامپیوتر نمونه داشته باشد، معمولاً روی اکثر کامپیوترهای دیگر نیز پیچیدگی زمانی از مرتبه (O(n² خواهدداشت. پس این نشانه به ما کمک می‌کند که صرف نظر از یک کامپیوتر خاص، یک حالت کلی برای پیچیدگی زمانی یک الگوریتم ارائه دهیم.<br />
پیچیدگی محاسباتی:<br />
هنگامی که یک الگوریتم خاص را تحلیل می کنیم ،پیچیدگی زمانی (یا حافظه ای) یا مرتبه پیچیدگی زمانی آن را تعیین می کنیم.عبارت است از مطالعه ی تمام الگوریتم های امکانپذبر برای حل یک مسئله مفروض است.در تحلیل پیچیدگی محاسباتی کوشش می کنیم تا حد پایینی کارایی همه الگوریتم ها را برای یک مسئله مفروض به دست آوریم.<br />
تحلیل پیچیدگی محاسباتی را با مطالعه ی مسئله مرتب سازی معرفی می کنیم.دو دلیل برای انتخاب مسئله وجود دارد.نخست چند مسئله ابداع شده اند که مسئله را حل می کنند.با مطالعه و مقایسه این الگوریتم ها،دیدی از چگونگی انتخاب از میان چند الگوریتم برای یک مسئله و بهبود بخشیدن به یک الگوریتم مفروض به دست می آوریم.<br />
دوم،مسئله مرتب سازی یکی از معدود مسائلی است که در بسط الگوریتم هایی با پیچیدگی زمانی نزدیک به حد پایینی از آن موفق بوده است.
 
== معرفی [[Np کامل]] ==
۱۵

ویرایش