そんな些細な質問で埋もれてしまうかと思いますが、ちょっと戸惑っています。
Java と C でクイックソートを実装し、いくつかの基本的な比較を行っていました。グラフは 2 つの直線として表示され、C は 100,000 のランダムな整数を超える Java の対応物よりも 4 ミリ秒高速でした。
私のテストのコードはここにあります。
(n log n) の線がどのように見えるかはわかりませんでしたが、直線になるとは思いませんでした。これが期待される結果であり、コード内のエラーを見つけようとしないことを確認したかっただけです。
式をExcelに貼り付けたところ、基数10の場合、最初にねじれのある直線のようです。これは、log(n) と log(n+1) の差が直線的に増加するためですか?
ありがとう、
ガブ
グラフを大きくすると、O(n logn) が完全に直線ではないことがわかります。しかし、はい、線形の動作にかなり近いです。理由を確認するには、いくつかの非常に大きな数の対数を取ります。
例 (基数 10):
log(1000000) = 6
log(1000000000) = 9
…
したがって、1,000,000 個の数値を並べ替えるには、O(n logn) 並べ替えではわずかに係数 6 が追加されます (ほとんどの並べ替えアルゴリズムは 2 を底とする対数に依存するため、それより少し多くなります)。ひどいことではありません。
実際、この対数係数は非常に小さいため、ほとんどの場合、確立された O(n logn) アルゴリズムは線形時間アルゴリズムよりも優れています。顕著な例は、サフィックス配列データ構造の作成です。
最近、基数ソートを使用して短い文字列のクイックソートソートを改善しようとしたときに、単純なケースに悩まされました。短い文字列の場合、この (線形時間) 基数ソートはクイックソートよりも高速ですが、基数ソートはソートする文字列の長さに大きく依存するため、比較的短い文字列には転換点がありました。
参考までに、クイックソートは実際には O(n^2) ですが、平均的なケースは O(nlogn) です。
参考までに、O(n) と O(nlogn) にはかなり大きな違いがあります。そのため、どの定数についても O(n) で制限できません。
グラフィカルなデモンストレーションについては、次を参照してください。
同様の方法でさらに楽しくするために、標準の素集合データ構造でn回の操作にかかる時間をプロットしてみてください。α( n ) がアッカーマン関数の逆関数である場合、漸近的にn α( n ) であることが示されています (ただし、通常のアルゴリズムの教科書では、おそらくn log log nまたはn log* nの範囲しか表示されません)。入力サイズとして遭遇する可能性が高いあらゆる種類の数値について、α( n ) ≤ 5 (実際には log* n ≤ 5) ですが、漸近的に無限大に近づきます。
このことから学べることは、漸近的複雑性はアルゴリズムを考える上で非常に役立つツールですが、実際の効率とはまったく同じではないということです。
したがって、O(n*log(n)) は少量のデータに対してのみ線形に似ています。
ヒント: クイックソートはランダム データに対して非常にうまく機能し、O(n*log(n)) アルゴリズムではないことを忘れないでください。
軸が正しく選択されていれば、任意のデータを線上にプロットできます:-)
ウィキペディアによると、Big-O は最悪のケースです (つまり、f(x) は O(N) であり、f(x) は N によって「上に制限されている」ことを意味します) https://en.wikipedia.org/wiki/Big_O_notation
これは、さまざまな一般的な関数の違いを示す素晴らしいグラフのセットです: http://science.slc.edu/~jmarshall/courses/2002/spring/cs50/BigO/
log(x) の導関数は 1/x です。これは、x が増加するにつれて log(x) が増加する速さです。ゆっくりと曲がるので直線に見えるかもしれませんが、直線的ではありません。O(log(n)) を考えるとき、私はそれを O(N^0+) と考えます。つまり、定数でない N の最小のべき乗です。これは、N の正の一定のべき乗が最終的にそれを追い越すためです。100%正確ではないので、そのように説明すると教授に怒られます。
2 つの異なる基数の対数の差は、一定の乗数です。2 つの底の間で対数を変換する式を調べます: (「底の変更」の下: https://en.wikipedia.org/wiki/Logarithm ) トリックは、k と b を定数として扱うことです。
実際には、通常、プロットするデータには何らかの問題が発生します。プログラムの外側に違いがあります (プログラムの前に CPU にスワップするもの、キャッシュ ミスなど)。信頼できるデータを取得するには、多くの実行が必要です。定数は、Big O 記法を実際のランタイムに適用しようとする最大の敵です。定数が大きい O(N) アルゴリズムは、N が十分に小さい場合、O(N^2) アルゴリズムよりも遅くなる可能性があります。
log(N) は (非常に) おおよそ N の桁数です。したがって、ほとんどの場合、log(n) と log(n+1) の間にほとんど違いはありません。
その上に実際の直線をプロットしてみると、わずかに増加することがわかります。50,0000 の Y 値は、100,000 の 1/2 Y 値よりも小さいことに注意してください。
ありますが、小さいです。これが O(nlog(n)) がとても良い理由です!