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

علم رایانه

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

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

پیچیدگی بدترین حالت تضمین می‌کند که در هر صورت (هر شکلی که این مقادیر و این روابط داشته باشند)، پیچیدگی الگوریتم مورد بحث حداکثر چه خواهد بود. معمولاً وقتی به نوع پیچیدگی (در بدترین حالت یا حالت متوسط یا ...) اشاره نمی‌شود، منظور نویسنده پیچیدگی در بدترین حالت است.[۲]

تعریف ویرایش

در یک مدل محاسباتی با فرض الفبای باینری، تمام ورودی‌های به طول   ممکن را با   نمایش می‌دهیم. فرض کنید برای الگوریتم   تابع   پیچیدگی الگوریتم را در حالات مختلف بدهد. مثلاً   یعنی اگر   و ۱۰ ورودی به ترتیب   به الگوریتم   داده شود، در آن صورت   با پیچیدگی   اجرا می‌شود.

پیچیدگی محاسباتی   در بدترین حالت ممکن به صورت زیر تعریف می‌شود: بیشینهٔ این پیچیدگی‌ها میان تمام حالات مختلف.[۳]

 

توصیف ویرایش

معمولاً پیچیدگی   را با نمادهای مجانبی توصیف می‌کنیم.

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

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

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

منابع ویرایش

  1. Introduction to Algorithms (CLRS) (3rd edition). به کوشش Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein.
  2. An Introduction to Formal Languages and Automata (6th edition). به کوشش Peter Linz.
  3. Introduction to the Theory of Computation (3rd edition). به کوشش Michael Sipser.