Worst-case complexity とは

コンピュータ科学では、最悪の場合の複雑さ(通常、漸近表記で示される)は、アルゴリズムが最悪の場合に必要とするリソース(例えば、実行時間、メモリ)を測定する。それは、アルゴリズムによって必要とされるリソースの上限を与える。
実行時間の場合、最悪の場合の時間複雑度は、サイズnの任意の入力を与えられたアルゴリズムによって実行される最長の実行時間を示し、これによりアルゴリズムが時間通りに終了することが保証される。さらに、最悪の場合の複雑さの成長の順序は、2つのアルゴリズムの効率を比較するために使用される。
アルゴリズムの最悪の場合の複雑さは、アルゴリズムがランダム入力で使用するリソース量の平均尺度である平均ケースの複雑さと対比されるべきです。