Intersezione di una superficie di un piano

Question

Sto cercando di scoprire quando un algoritmo di selezione quadratica è più veloce di un algoritmo di selezione lineare. L'uso di alcuni esperimenti ho generato due trame 3D che mostrano i tempi di esecuzione dell'algoritmo in funzione delle dimensioni array e la statistica ordine desiderato. Utilizzando gnuplot per disegnare la trama mi ha confermato che non ci sono casi in cui l'algoritmo quadratico è più veloce. Ho quindi utilizzato algoritmi di adattamento di gnuplot per trovare due funzioni che modellano i miei tempi di esecuzione osservati (a, b, c, d, e, f sono costanti ho già trovato, ma lasciare fuori):

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

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

dove x è la dimensione della matrice di input ed y è la statistica ordine.

Ora sto tipo di Lost su come utilizzare questi modelli per calcolare quando per passare tra l'attuazione quadratica e l'implementazione lineare. Ho il sospetto che devo trovare dove queste due funzioni si intersecano ma non sono del tutto sicuro di come farlo. Come si trova in cui queste due funzioni si intersecano?

Answer 1

In sostanza si vuole usare l'algoritmo che ha la stima di esecuzione più basso.

Si può solo calcolare il valore di ciascuno dei tempi di esecuzione previsti, e utilizzare l'algoritmo con il valore più basso. È possibile semplificare questo leggermente.

Si desidera utilizzare l'algoritmo quad quando:

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

Pertanto è possibile calcolare ax + by -dexy + c-f e se è inferiore a zero, utilizzare l'algoritmo quadratico.