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

جز (ابرابزار)
برچسب: نیازمند بازبینی
پیچیدگی محاسباتی:{{سخ}}
هنگامی که یک الگوریتم خاص را تحلیل می‌کنیم، پیچیدگی زمانی (یا حافظه‌ای) یا مرتبه پیچیدگی زمانی آن را تعیین می‌کنیم. عبارت است از مطالعهٔ تمام الگوریتم‌های امکانپذبر برای حل یک مسئله مفروض است. در تحلیل پیچیدگی محاسباتی کوشش می‌کنیم تا حد پایینی کارایی همه الگوریتم‌ها را برای یک مسئله مفروض به دست آوریم.{{سخ}}
تحلیل پیچیدگی محاسباتی را با مطالعهٔ مسئله مرتب‌سازی معرفی می‌کنیم. دو دلیل برای انتخاب مسئله وجود دارد. نخست چند مسئلهالگوریتم ابداع شده‌اند که مسئله را حل می‌کنند. با مطالعه و مقایسه این الگوریتم‌ها، دیدی از چگونگی انتخاب از میان چند الگوریتم برای یک مسئله و بهبود بخشیدن به یک الگوریتم مفروض به دست می‌آوریم.{{سخ}}
دوم، مسئله مرتب‌سازی یکی از معدود مسائلی است که در بسط الگوریتم‌هایی با پیچیدگی زمانی نزدیک به حد پایینی از آن موفق بوده است.
 
کاربر گمنام