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

پیچیدگی محاسباتی:{{سخ}}

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

دوم، مسئله مرتب‌سازی یکی از معدود مسائلی است که در بسط الگوریتم‌هایی با پیچیدگی زمانی نزدیک به حد پایینی از آن موفق بوده است.