バブルソート、挿入ソートなどは知っていますが、より効率的なソートアルゴリズムがあります。時間階層定理により、任意の実数 r < 2 に対して、O(n^2) では解決できるが O(n^r) では解決できない問題があります。その証明に使用される構成はあまり自然ではありません。最も効率的な解が 2 次時間を必要とする問題の良い例は?
できれば次の性質を備えたものを探しています。
小さな注意点 - 出力は大きくしないでください。(指定されたリストから整数のすべてのペアの合計が必要な場合は、それらを出力するために明らかに二次時間が必要です)。これは決定問題、つまりイエスかノーで答えられる問題であると考えることができます。また、時間計算量 O(n^2) が入力サイズの関数であると仮定します。つまり、n は入力を表すのに必要なビット数です。
n 2個のすべてのエントリを処理する必要があるため、行列乗算には Ω( n 2 )の理論的な下限があります。これまでで最もよく知られているアルゴリズム (上記リンクのウィキペディアの記事によると) の複雑さは O( n 2.3727 ) です。単純なアルゴリズムの複雑さはn 3です。
数学的操作の計算の複雑さに関するウィキペディアの記事によると、n 個の解を取得するための三角行列の逆代入は O( n 2 ) です。ウェブ上にはおそらく他にも多くの例があります。
EDIT：ミケーレ・ボラッシらによる2014年の論文。は、任意のε > 0 に対して O( n 2 ) 時間で解決できますが、O( n 2- ε ) では解決できない多くの決定問題 (出力サイズ O(1)) について説明しています。(もちろん、いつものように、これらは結果は P ≠ NP に依存するか、より正確には、強指数時間仮説が真であることに依存します。)
彼らの論文は、修正されたk -SAT 問題で始まります。
入力：
出力: trueすべての節を満たすすべての変数の評価がある場合、Falseそうでない場合。
修正されていないk -SAT 問題 (入力に上記の 3 番目の黒丸が含まれていない場合) は NP 完全であるため、通常は指数時間の問題と見なされることに注意してください。ただし、ここでは入力サイズ自体が変数の数で指数関数的です。彼らは、この変更により、問題は常に 2 次時間で解決できることを示しています (単純にすべての可能な評価を試してみてください)。この回答の要点は、これが問題を解決するアルゴリズムの最小の時間の複雑さであることも示しています。
この修正されたk -SAT 問題は非常に自然であると反論する人もいるかもしれません。ただし、彼らはこれを使用して、自然に見える他の多くの問題も O( n 2 ) 時間未満では解決できないことを示しています。述べる最も簡単なものはサブセットグラフ問題です:
入力:セットXとXのサブセットのコレクションC。
出力:グラフG = ( C , E )、ここで、各Cについて、C ′ ∈ C、( C , C ′) ∈ Eは、 C ⊆ C ′ の場合に限ります。
あなたは計算モデルを混合するという根本的な間違いを犯しています。
時間階層定理はチューリングマシンに関するものですが、他のほとんどの境界には独自のモデル（並べ替えの比較モデルなど）があるか、通常はRAMモデルに関するものです。
ですから、本当の問題は、どの計算モデルについて話しているのかということです。
また、O（n ^ 2）（BigOh）より悪くない最良のアルゴリズムについて話すのはナンセンスです。BigOHは上限です。あなたはおそらくシータを使うつもりだったでしょう。
これはほぼ 1 年後のことですが、私には答えがあると思います。半順序の発見です。
全体の順序でソートすることを少し考えてみてください。n 個のオブジェクトのシーケンス (これらは異なるものと仮定します) と、2 つの要素をテストして一方が他方より小さいかどうかを確認する比較操作があります。
要素がどの順列にあるかを発見しようとしています。n! 個あります。可能な順列なので、1 から n! までの数を見つけようとしています。比較するたびに、1 ビットの情報が得られます。1からnまでの数を発見するために！log(n!) ビットを検出する必要があります。したがって、必要な比較の数も log(n!) ビット、つまり次のようになります。
log(n!) = n log n + o(n log n) = Ω(n log n) ビット
(もちろん、すべての対数は底が 2 です。)
これ以上のことはできません。各クエリが 1 ビットの情報を提供し、少なくとも Ω(n log n) ビットを検出する必要がある場合、Ω(n log n) 比較が必要です。もっとうまくやれると思うなら、シャノン、チャイティン、コルモゴロフと一緒にやってみてください。
しかし、さらに優れているのは、最悪の場合でもそれを実行できるアルゴリズムが知られていることです (例: ヒープ ソート)。その意味で、ヒープソートは漸近的に最適です。
（複数ビットの情報を返すクエリ操作がある場合は、より適切に実行できることに注意してください。たとえば、Ω（log n）ビットを返すクエリ操作を考え出すことができれば、Ωでソートできるはずです(n) 時間。詳細については、基数ソートを参照してください。)
この分析は、あらゆる種類のアルゴリズムで機能します。n 個の一連のものの中から 1 個のものを見つけるには、1 から n の間の数を発見する必要があります。つまり、log n + O(1) ビットを発見することを意味します。クエリ操作が 1 ビットを返す場合、検索には Ω(log n) クエリが必要です。(詳細については、二分探索を参照してください。)
これで私がどこに向かっているのかがわかると思います。
ここで、半順序関係を持つ n 個の要素があるが、それが何であるかわからず、調べたいとします。ただし、2 つの要素 x と y を比較し、半順序で x が y 以下の場合に「true」を返すクエリがあります。
Ω(n^2) 時間かかる半順序を発見する明白なアルゴリズムがあります: 各要素を他の要素と比較するだけです。
しかし、これは最適ですか？さて、クエリ操作は 1 ビットの情報を返します。n 個の要素の半順序の数は、Sloane の A001035によって与えられます。私が正しく読んでいれば、このシーケンスは Ω(2^(n^2)) です。つまり、半順序を発見するには、次のものが必要です。
Ω(log 2^(n^2)) = Ω(n^2) ビット
つまり、Ω(n^2) 時間を超えることはできないため、これは漸近的に最適なアルゴリズムです。
「それで」、「入力のサイズが n であるという事実を購入します。しかし、出力のサイズはO(n^2) ではないので、実際には深い技術的な意味で線形アルゴリズムです。」 ？」
うーん...多分。今は詳細に入る時間があまりありませんが、質問でお答えします。
昔ながらの並べ替えの場合、n 個の個別の要素が与えられることがあります。区別するには、n 個の異なるラベルでラベル付けする必要があります。n 個の個別のラベルを格納するということは、それぞれが 1 から n の間の n 個の数値を格納することを意味します。これらの各数値を表すには log n ビットが必要なので、問題の合計サイズは n log nビットになります。では、ヒープの並べ替えは問題のサイズに線形であると言ってみませんか?