上限、下限

Question

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

Answer 1

上限を証明するということは、アルゴリズムがリソースの制限をわずか使用することを証明したことを意味します。

下限を証明するということは、アルゴリズムがリソースの制限を少なからず使用することを証明したことを意味します。

＆quot;リソース＆quot;このコンテキストでは、時間、メモリ、帯域幅などが考えられます。

Answer 2

上限と下限は、最小と最大の「複雑さ」に関係しています。アルゴリズムの（複雑さの分析で非常に特定の意味を持っているので、私はその言葉を賢く使用します）。

たとえば、私たちの旧友であるバブルソートを見てください。すべてのデータが既にソートされている理想的な場合、かかる時間はf（n）で、リスト内のアイテムの数である 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）であると言います。上限は、直感的に、特定のアルゴリズムが問題を解決するのにどれほど優れているかを教えてくれます。