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

در علوم کامپیوتر و در نظریه پیچیدگی محاسباتی، پیچیدگی بدترین حالت یک کران بالا برای پپیچیدگی محاسباتی یک الگوریتم فراهم می‌کند.

بیشتر الگوریتم‌ها بر اساس ویژگی‌های ورودی رفتار (پیچیدگی) متفاوتی دارند. به عنوان مثال در الگوریتم‌های مرتب‌سازی میزان پیچیدگی را بر حسب طول آرایه ($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$ در بدترین حالت ممکن به صورت زیر تعریف می‌شود: بیشینهٔ این پیچیدگی‌ها میان تمام حالات مختلف.

$T_{max_{A}}(n):=\max _{s\in \{0,1\}^{n}}t_{A}(s)$

توصیف

معمولاً پیچیدگی $T_{max_{A}}\!(n)$ را با نمادهای مجانبی توصیف می‌کنیم.

مثلاً در مرتب‌سازی حبابی بهترین حالت برای الگوریتم زمانی پیش می‌آید که اعداد از قبل مرتب باشند و در آن صورت پیچیدگی آن ${\mathcal {O}}(n)$ می‌شود. همچنین بدترین حالت زمانی است که اعداد از آخر به اول مرتب باشند و در آن صورت پیچیدگی آن ${\mathcal {O}}(n^{2})$ می‌شود. بنابراین می‌گوییم پیچیدگی محاسباتی این الگوریتم در بدترین حالت از ${\mathcal {O}}(n^{2})$ است. به این معنی که نرخ رشد $T_{max_{A}}\!(n)$ از $n^{2}$ کمتر یا مساوی است (در اینجا مساوی است).

توجه کنید که لزومی ندارد که از نماد ${\mathcal {O}}(n^{2})$ استفاده کنیم. می‌توان $T_{max_{A}}\!(n)$ را با $\Omega (n^{2})$ هم توصیف کرد. به این معنی که نرخ رشد $T_{max_{A}}\!(n)$ (یا پیچیدگی محاسباتی الگوریتم در بدترین حالت) از $n^{2}$ بیشتر یا مساوی است (در این مثال مساوی است).

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

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