Intersecção de uma superfície de um plano de

Question

Eu estou tentando descobrir quando um algoritmo de seleção quadrática é mais rápido do que um algoritmo de seleção linear. Executando algumas experiências que gerou dois 3D lotes que mostram os tempos algoritmo executado como uma função do tamanho da matriz de entrada e a estatística ordem desejada. Usando gnuplot para desenhar o gráfico I confirmou que há casos em que o algoritmo quadrática é mais rápido. Eu, então, algoritmos de montagem do gnuplot usado para encontrar duas funções que modelo meus tempos de execução observados (a, b, c, d, e, f são constantes Eu já encontrados, mas deixar de fora):

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

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

onde x é a dimensão da matriz de entrada e y é a ordem estatística.

Agora estou meio perdido sobre como usar esses modelos para calcular quando alternar entre a aplicação quadrática ea implementação linear. Eu suspeito que eu tenho que descobrir onde essas duas funções se cruzam, mas não tenho certeza de como fazer isso. Como se encontra onde essas duas funções se cruzam?

Answer 1

Basicamente, você quer usar o algoritmo que tem a menor estimativa de tempo de execução.

Você pode apenas calcular o valor de cada um dos tempos de execução estimados, e usar o algoritmo com o menor valor. Você pode simplificar isso muito ligeiramente.

Você quer usar o algoritmo quad quando:

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

Por isso você pode calcular ax + by -dexy + c-f e se é menor que zero, usar o algoritmo quadrática.