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

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

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

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

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

تعاریف

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

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

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

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

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

توصیف

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

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

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

منابع

1. Introduction to Algorithms (CLRS) (3rd edition). به کوشش Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein.
2. O. Goldreich and S. Vadhan, Special issue on worst-case versus average-case complexity, Comput. Complex. 16, 325–330, 2007.