4

比較ベースの並べ替えは nlog(n) の大きなオメガであるため、mergesort をO(n)にすることはできません。それにもかかわらず、次の証明で問題を見つけることができません。

命題P(n) : 長さnのリストの場合、mergesort はO(n)時間かかります。

P(0) : 空のリストのマージ ソートは空のリストを返します。

強い帰納法: P(1), ..., P(n-1)を仮定し、 P(n )を証明しようとします。再帰的なマージソートの各ステップで、2 つのほぼ「半分のリ​​スト」がマージソートされてから「圧縮」されることがわかっています。各ハーフリストのマージソートには、帰納法によりO(n/2) 時間かかります。圧縮にはO(n)時間がかかります。したがって、アルゴリズムには、M(n) = 2M(n/2) + O(n)の再帰関係があり、これは2O(n/2) + O(n)であり、O(n)です。

4

3 に答える 3

7

線形探索が O(1) であるという「証明」を比較してください。

  1. 空の配列の線形検索は O(1) です。
  2. 空でない配列の線形検索は、最初の要素 (O(1)) を比較してから、配列の残り (O(1)) を検索します。O(1) + O(1) = O(1)。

ここでの問題は、帰納法が機能するためには、仮説と結論の両方で機能する 1 つの大きな定数が必要であるということです。それはここでは不可能であり、あなたの証明も不可能です。

于 2011-11-14T20:37:38.993 に答える
4

「証明」は単一のパスのみをカバーし、log n回のパスはカバーしません。

再発は、前のパスのコストと比較したパスのコストのみを示します。正確に言えば、反復関係には増分コストではなく累積コストが含まれている必要があります。

http://en.wikipedia.org/wiki/Merge_sortでマージソートのサンプルを表示することで、証明がどこに分類されるかを確認できます。

于 2011-11-14T20:30:13.193 に答える
3

ここに重要な点があります: n の特定の値を参照するすべての誘導ステップは、O() 表記ではなく、特定の関数 T(n) を参照する必要があります!

O(M(n)) 表記は、問題のサイズからパフォーマンスの保証までの関数全体の動作に関するステートメントです(漸近的に、n は無制限に増加します)。誘導の目標は、パフォーマンスの限界 T(n) を決定することです。これは、(定数と低次の要素を削除することによって) O(M(n)) に単純化できます。

特に、証明の 1 つの問題は、純粋に O() に関するステートメントから、特定の n に対する T(n) に関するステートメントに戻ることができないことです。O() 表記を使用すると、関数全体の定数係数を無視できます。同じ関数を再帰的に構築している間、定数因子を何度も無視することはできません...

O() 表記を使用して証明を単純化することもできます:

T(n) = F(n) + O(something less significant than F(n))

そして、この述語を通常の帰納的な方法で伝播します。ただし、F() の定数係数を保持する必要があります。この定数係数は、分割統治の繰り返しの解決に直接関係しています。

于 2011-11-15T00:18:54.270 に答える