پیچیدگی حالت متوسط

در نظریهٔ پیچیدگی محاسباتی، پیچیدگی حالت متوسط یک الگوریتم (برخلاف پیچیدگی بدترین حالت) مقدار متوسط پپیچیدگی محاسباتی یک الگوریتم را ارائه می‌کند.

بیشتر الگوریتم‌ها بر اساس ویژگی‌های ورودی رفتار (پیچیدگی) متفاوتی دارند. به عنوان مثال در الگوریتم‌های مرتب‌سازی میزان پیچیدگی را بر حسب طول آرایه ($n$) بررسی می‌کنیم، در حالی که بسیاری از این الگوریتم‌ها به متغیرهای دیگری نیز بستگی دارند؛ مثلاً این که این $n$ عدد چه اعدادی باشند یا چه رابطه‌ای با یکدیگری داشته باشند.

پیچیدگی حالت متوسط بیان می‌کند که به‌طور متوسط (بین اشکالی که این مقادیر و این روابط ممکن است داشته باشند)، پیچیدگی الگوریتم مورد بحث چه خواهد بود.

سه انگیزه اصلی برای مطالعه پیچیدگی حالت متوسط وجود دارد. ممکن است برخی مسائل در بدترین حالت عملکرد بسیار ضعیفی داشته باشند اما این حالت‌های بد بسیار نادر باشند؛ بنابراین پیچیدگی حالت متوسط ممکن است معیار دقیق‌تری برای عملکرد یک الگوریتم باشد. پیچیدگی حالت متوسط اجازه می‌دهد تا کارآمدترین الگوریتم در دنیای واقعی را در میان چند الگوریتم (مثل مرتب‌سازی سریع) تشخیص دهیم. همچنین تحلیل پیچیدگی متوسط ابزارهایی را فراهم می‌کند که برای ایجاد نسخه‌های سخت مسائل استفاده می‌شوند و می‌توانند در زمینه‌هایی مانند رمزنگاری و تصادفی سازی مورد استفاده قرار گیرند.

تعاریف

تعریفی مشابه تعریف پیچیدگی بدترین حالت به این صورت است:

در یک مدل محاسباتی با فرض الفبای باینری، تمام ورودی‌های به طول $n$ ممکن را با $\{0,1\}^{n}$ نمایش می‌دهیم. فرض کنید برای الگوریتم $A$ تابع $t_{A}\colon \{0,1\}^{n}\to \mathbb {N}$ پیچیدگی الگوریتم را در حالات مختلف بدهد؛ مثلاً $t_{A}(0100111110)=20$ یعنی اگر $n=10$ و ۱۰ ورودی به ترتیب $0100111110$ به الگوریتم $A$ داده شود، در آن صورت $A$ با پیچیدگی $20$ اجرا می‌شود.

حالت متوسط پیچیدگی محاسباتی $A$ را به این صورت تعریف می‌کنیم: میانگین این پیچیدگی‌ها میان تمام حالات مختلف. به عبارتی دیگر در تحلیل احتمالاتی، با فرض این که احتمال پیشامد هر ورودی ممکن (متغیر تصادفی) از $\{0,1\}^{n}$ یکسان باشد، امید ریاضی پیچیدگی $t_{A}$ را $T_{avg_{A}}$ می‌نامیم.

$T_{avg_{A}}(n):=\mathbb {E} (t_{A})=\left(\sum _{s\in \{0,1\}^{n}}t_{A}(s)\right)/|\{0,1\}^{n}|$

در بیشتر مواقع فرض توزیع یکنواخت فرض معقولی است ولی شاید گاهی نیاز باشد امید ریاضی را با فرض دیگری حساب کنیم.

توصیف

پیچیدگی $T_{avg_{A}}$ را با نمادهای مجانبی توصیف می‌کنیم؛ مثلاً در مرتب‌سازی سریع، پیچیدگی بدترین حالت ${\mathcal {O}}(n^{2})$ است در حالی که در حالت متوسط $T_{avg_{A}}\thicksim 2n\ln n$ است.

جستارهای وابسته

• پیچیدگی در بدترین حالت
• تحلیل الگوریتم