4

複雑さがO（nlogn）である「ヒープソート」メソッドがあるとします。1000000入力でこのメソッドの実行時間を測定すると、0.375770669秒になりました。このメソッドの実行時間を理論的に計算するにはどうすればよいですか？

4

3 に答える 3

5

これを理論的に計算する方法はありません。それは次のような多くの要因に依存します：

  • javaエディションとメジャー/マイナー/パッチのリリース番号。
  • さまざまなJVMチューニングパラメータ。たとえば、ヒープの大きさ。
  • ハードウェアプラットフォーム。CPU、メモリサイズ、さらにはマザーボードとクロック速度。
  • マシンの負荷。つまり、他に何をしているのか。
  • CPUヒートシンクの綿毛の量。真剣に...プロセッサチップが熱くなりすぎるとクロック速度が低下する可能性があり、マザーボードの発振器のクロック速度も（少し）温度に敏感です。

これらすべてを知っていたとしても、計算は基本的にJavaJITコンパイラとハードウェア実行のフォレンジックシミュレーションになります。考えるには複雑すぎます。

「速度」の理論的尺度に関して合理的に期待できる最善の方法は、ソースコードレベルで抽象操作をカウントすることです。ドリルダウンして実行されたバイトコードをカウントすることでさえ、おそらく実用的であるには難しすぎます。

測定したものと理論的なものを比較したいと思います。

基本的にはできません。

于 2011-05-20T04:48:35.973 に答える
2

おそらくできることは、1000、10000、100000、1000000、10000000などのさまざまな数の入力に対してコードを実行し、並べ替えに費やされた時間を記録することです。次に、それらのレコード時間をXYグラフの要素数に対してプロットし、O(nlogn)複雑さの曲線が得られるかどうかを確認します。

ヒープソートの分析とデモについては、次のドキュメントも参照してください：http: //www.inf.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm

于 2011-05-20T04:49:15.683 に答える
1

O（・）またはΘ（・）表記は、nが無限大に近づくときの限界で、漸近的な成長率を表すことを忘れないでください。たとえば、入力サイズに10を掛けたときにアルゴリズムがどれだけ遅くなるかを表します。これが実際の入力サイズ（「無限大」と比較して常に無限に小さい）の実際の実行時間にどれだけ密接に対応するかは、アルゴリズムの分析に使用される理論モデルが実際のマシンにどれだけ密接に対応するかによって異なります。

具体的には、「ヒープソートにはΘ（n log n）時間がかかる」とは、定数c1とc2が存在することを意味します。したがって、nが十分に大きい場合、T（n）がサイズnの入力にかかる時間であるとすると、

c 1 n log n <T（n）<c 2 n log n

n = 1000000のサイズは、漸近的な動作を開始するために「十分に大きいn」である場合とそうでない場合があります。

それにもかかわらず、それがそうであると仮定し、かかる時間がおおよそ（cn log n）であるという意味でステートメントを解釈すると、定数cは、次のようになります。

c1000000lg（1000000）=0.375770669秒

c≈1.88× 10-8を与えます。これは、サイズn = 2000000の入力には約0.79秒かかり、n=10000000の入力には約4.38秒かかることを意味します。この「理論的」結果を、そのサイズの入力でアルゴリズムを実行することによって得られる実験結果と比較できます。

一般的なコンピューターの大まかな目安として、cは低速のコンピューターとアルゴリズムの場合は10 -7の間、適度に適切なコンピューターの場合は10-9の間です。安全のために、両端でさらに10の因数を掛けます。（一般的な分析では定数cがたとえば1〜200のどこかにあり、一般的なコンピューターの速度は1〜2桁以内であるという考え方です。もちろん、「一般的な」は主観的なものであり、フィボナッチでこれを試してみると、おそらくがっかりするでしょう。）

先験的なcの推測から始めると、実行時間は約0.2秒であるとすると約10-8になります。

于 2011-05-20T05:19:22.707 に答える