Intersection d'une surface d'un plan

Question

J'essaie de savoir quand un algorithme de sélection quadratique est plus rapide qu'un algorithme de sélection linéaire. En exécutant quelques expériences, j'ai 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 de la statistique d'ordre désirée. En utilisant gnuplot pour dessiner l'intrigue j'ai confirmé qu'il y a des cas où l'algorithme quadratique est plus rapide. J'ai ensuite utilisé les algorithmes d'ajustement de gnuplot pour trouver deux fonctions qui modélisent mes temps d'exécution observés (a, b, c, d, e, f sont des constantes que j'ai déjà trouvées):

lin_alg_runtime (x, y) = un 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 quand passer de l'implémentation quadratique à l'implémentation linéaire. Je suppose que je dois trouver où ces deux fonctions se croisent, mais je ne suis pas sûr de savoir comment faire. Comment trouve-t-on l'intersection de ces deux fonctions?

Answer 1

Fondamentalement, vous voulez utiliser l'algorithme ayant l'estimation d'exécution la plus faible.

Vous pouvez simplement calculer la valeur de chacun des temps d'exécution estimés et utiliser l'algorithme ayant la valeur la plus faible. Vous pouvez simplifier cela 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.