algorithm - 上限、下限

Question

アルゴリズムの上限または下限を証明するとはどういう意味ですか?

Answer 1

上限を証明するということは、アルゴリズムがリソースに対してある程度の制限しか使用しないことを証明したことを意味します。

下限を証明するということは、アルゴリズムがリソースに対して少なくともある程度の制限を使用することを証明したことを意味します。

このコンテキストでの「リソース」は、時間、メモリ、帯域幅、またはその他のものである可能性があります。

Answer 2

上限と下限は、アルゴリズムの最小および最大の「複雑さ」と関係があります（複雑さの分析では非常に特殊な意味があるため、この単語を使用することをお勧めします）。

たとえば、私たちの旧友であるバブルソートを考えてみましょう。nすべてのデータがすでに並べ替えられている理想的なケースでは、かかる時間はf（n）です。これは、リスト内のアイテムの数に依存する関数です。これは、リストが確実にソートされるようにするには、データセットを1回パスするだけでよいためです（スワップはゼロ）。

データが希望の順序とは逆に並べ替えられる特に悪いケースでは、かかる時間はf（n ²）になります。これは、各パスが1つの要素を正しい位置に移動し、nすべての要素を実行するにはパスが必要なためです。

その場合、big-Oの複雑さは同じままですが、上限と下限は異なります。

余談ですが、バブルソートは（通常は正当な理由で）非常に悪意がありますが、特定の状況では意味があります。私は実際に、データの大部分がすでに並べ替えられており、リストの最後に一度に1つか2つの項目しか追加されない傾向があるアプリケーションで使用しています。1つのアイテムを追加する場合、および逆方向のバブルソートを使用すると、新しいリストが1回のパスでソートされることを保証できます。これは、下限の概念を示しています。

実際、リストがソートされているかどうかを示す追加のデータを提供するだけで、下限をf（1）に設定するバブルソートを最適化できます。並べ替え後にこれを設定し、最後にアイテムを追加するときにクリアします。

Answer 3

境界 (上限または下限) がどうであれ、考慮できる最悪の場合の入力について常に話しています。たとえば、並べ替えでは、最悪のケースは並べ替えられていない入力リストであると想定しています。

私の理解では、問題には下限があります。たとえば、比較ベースの並べ替えの下限は \Omega(n log n) であると言います。使用する特定の比較ベースの並べ替えアルゴリズムについては想定していません。アルゴリズム (マージ ソート、クイック ソートなど) が何であれ、\Omega(n log n) のこの境界を超えることはできません。下限は、特定の問題がどれほど難しいかを直感的に教えてくれます。

特定のアルゴリズムについて話すときは、上限について話します。例えば、バブルソートの上限をO(n^2)、マージソートの上限をO(n log n)とします。上限は、直観的に、特定のアルゴリズムが問題を解決するのにどれだけ優れているかを教えてくれます。