1

二次選択アルゴリズムが線形選択アルゴリズムよりも高速な場合を見つけようとしています。いくつかの実験を実行して、アルゴリズムの実行時間を入力配列サイズと目的の次数統計の関数として示す 2 つの 3D プロットを生成しました。gnuplot を使ってプロットを描く 2 次アルゴリズムの方が速い場合があることを確認しました。次に、gnuplot のフィッティング アルゴリズムを使用して、観測されたランタイムをモデル化する 2 つの関数を見つけました (a、b、c、d、e、f は、既に見つけた定数ですが省略します)。

lin_alg_runtime(x,y) = a x + b y +c

quad_alg_runtime(x,y) = (d*x * e*y) + f

ここで、x は入力配列のサイズで、y は順序統計です。

今、これらのモデルを使用して、二次実装と線形実装をいつ切り替えるかを計算する方法がわかりません。これら 2 つの関数が交差する場所を見つける必要があると思いますが、その方法がよくわかりません。これら 2 つの関数が交差する場所をどのように見つけますか?

4

1 に答える 1

1

基本的に、実行時間の見積もりが最も低いアルゴリズムを使用する必要があります。

それぞれの推定実行時間の値を計算し、最小値のアルゴリズムを使用するだけです。これをごくわずかに単純化できます。

次の場合に quad アルゴリズムを使用します。

qual_alg_runtime(x,y) < lin_alg_runtime(x,y)
ax + by + c < dxey + f
ax + by -dexy + c-f < 0

したがって、計算できax + by -dexy + c-f、ゼロ未満の場合は二次アルゴリズムを使用します。

于 2009-12-02T04:30:21.533 に答える