表面の交点プレーン

Question

私は、二次選択アルゴリズムは線形選択アルゴリズムよりも速い場合を見つけるためにしようとしています。私は、入力配列のサイズと所望の順序統計量の関数として、アルゴリズムの実行時間を表示する2つの3Dプロットを生成したいくつかの実験を実行しています。私は、二次アルゴリズムが速い場合場合があることを確認したプロットを描画するためにはgnuplotを使用しました。私はその後、私の観察ランタイム（A、B、C、D、E、Fは、私はすでに見つけた定数であるが、うちのまま）モデルの二つの機能を見つけるためにはgnuplotのフィッティングアルゴリズムを使用します：

lin_alg_runtime（x、y）は、 X + B Y + C

を=

quad_alg_runtime（X、Y）=（D * X *イー・Y）+ F

Xは入力配列とyの大きさ順序統計量である。

今、私は一種の二次実装とリニア実装を切り替えること際の計算にこれらのモデルを使用する方法に迷ってしまいました。私はこの2つの関数が交差する場所を見つけるために持っている疑いがあるが、私はそれを行う方法はかなりわかりません。これら二つの機能が交差どのようにして見つけるのでしょうか？

Answer 1

基本的には、最低の実行時の見積もりを持っているアルゴリズムを使用します。

あなただけの推定実行時間のそれぞれの値を計算し、最も低い値とアルゴリズムを使用することができます。あなたは非常にわずかにこれを簡素化することができます。

あなたはときクワッドアルゴリズムを使用したいです

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を計算することができ、それがゼロ未満だ場合、次のアルゴリズムを使用します。