Intersection d'une surface d'un plan

Question

Je suis en train de savoir quand un algorithme de sélection du second degré est plus rapide qu'un algorithme de sélection linéaire. Exécution de quelques expériences que je généré deux tracés 3D qui montrent les temps d'exécution de l'algorithme en fonction de la taille du tableau d'entrée et la statistique de l'ordre souhaité. En utilisant gnuplot pour dessiner l'intrigue, je confirme qu'il ya des cas où l'algorithme du second degré est plus rapide. J'ai ensuite utilisé des algorithmes d'ajustement de gnuplot pour trouver deux fonctions qui modélisent mes runtimes observées (a, b, c, d, e, f sont des constantes que je l'ai déjà trouvé, mais omettent):

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

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

où x est la taille de la matrice d'entrée et y est la statistique d'ordre.

Maintenant, je suis un peu perdu sur la façon d'utiliser ces modèles pour calculer le moment pour basculer entre la mise en œuvre du second degré et la mise en œuvre linéaire. Je pense que je dois trouver où ces deux fonctions se croisent mais je ne suis pas tout à fait sûr de savoir comment faire. Comment peut-on trouver où ces deux fonctions se croisent?

Answer 1

Fondamentalement, vous voulez utiliser l'algorithme qui a l'estimation d'exécution le plus bas.

Vous pouvez simplement calculer la valeur de chacun des runtimes estimés, et utiliser l'algorithme avec la valeur la plus basse. Vous pouvez simplifier cette très légèrement.

Vous voulez utiliser l'algorithme quad lorsque:

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

Par conséquent, vous pouvez calculer ax + by -dexy + c-f et si elle est inférieure à zéro, utilisez l'algorithme quadratique.