Intersección de una superficie de un plano

Question

Estoy tratando de averiguar cuándo un algoritmo de selección cuadrática es más rápido que un algoritmo de selección lineal. La ejecución de algunos experimentos que generan dos parcelas en 3D que muestran los tiempos de ejecución algoritmo en función del tamaño de la matriz de entrada y la estadística de orden deseado. El uso de gnuplot para dibujar la superficie confirmé que hay casos en que el algoritmo cuadrática es más rápido. Luego utiliza algoritmos de ajuste de gnuplot para encontrar dos funciones que modelan mis tiempos de ejecución observados (a, b, c, d, e, f son constantes ya he encontrado, pero dejan de lado):

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

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

donde x es el tamaño de la matriz de entrada e y es la estadística de orden.

Ahora estoy un poco perdido sobre cómo utilizar estos modelos para calcular cuándo cambiar entre la aplicación cuadrática y la aplicación lineal. Sospecho que tengo que buscar donde se cruzan estas dos funciones, pero no estoy muy seguro de cómo hacerlo. ¿Cómo se encuentra donde se cruzan estas dos funciones?

Answer 1

Básicamente desea utilizar el algoritmo que tiene la estimación más baja en tiempo de ejecución.

Usted sólo puede calcular el valor de cada uno de los tiempos de ejecución estimado, y utilizar el algoritmo con el valor más bajo. Se puede simplificar esta muy ligeramente.

Usted desea utilizar el algoritmo quad cuando:

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

Por lo tanto se puede calcular ax + by -dexy + c-f y si es menor que cero, utilice el algoritmo cuadrático.