Kreuzung einer Oberfläche Ein Flugzeug

Question

Ich versuche, herauszufinden, wann ein quadratischer Auswahlalgorithmus schneller als ein linearer Auswahlalgorithmus ist. Laufen einiger Experimente erzeugen ich zwei 3D-Plots, dass die Algorithmus Laufzeiten in Abhängigkeit von der Eingangsfeldgröße und der gewünschten Reihenfolge Statistik zeigen. Mit gnuplot den Plot zeichnen ich bestätigt, dass es Fälle gibt, wenn der quadratischen Algorithmus schneller ist. Früher habe ich dann gnuplot der Anpassungsalgorithmen zwei Funktionen zu finden, die meine beobachtete Runtimes Modell (a, b, c, d, e, f Konstanten sind, habe ich schon gefunden habe, aber auslassen):

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

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

, wobei x die Größe des Eingangsfeldes ist und y die Ordnungsstatistik.

Jetzt bin ich irgendwie verloren, wie diese Modelle zu verwenden, um zu berechnen, wenn zwischen der quadratischen Ausführung und der linearen Umsetzung zu wechseln. Ich vermute, ich habe zu finden, wo diese beiden Funktionen schneiden, aber ich bin mir nicht ganz sicher, wie das zu tun. Wie findet man, wo diese beiden Funktionen schneiden?

Answer 1

Im Grunde wollen Sie den Algorithmus verwenden, der die niedrigste Laufzeitschätzung hat.

Sie können nur den Wert jedes der geschätzten Laufzeiten, berechnen und den Algorithmus mit dem niedrigsten Wert verwenden. Sie können dies vereinfachen sehr leicht.

Sie möchten den Quad-Algorithmus verwenden, wenn:

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

Sie können also ax + by -dexy + c-f berechnen und wenn es kleiner als Null ist, den quadratischen Algorithmus verwenden.