Пересечение поверхности с плоскостью

Question

Я пытаюсь выяснить, когда алгоритм квадратичного выбора быстрее, чем алгоритм линейного выбора. Проведя несколько экспериментов, я сгенерировал два 3D-графика, которые показывают время выполнения алгоритма в зависимости от размера входного массива и желаемой статистики заказа. Используя gnuplot для рисования графика, я подтвердил, что есть случаи, когда квадратичный алгоритм работает быстрее. Затем я использовал алгоритмы подбора gnuplot, чтобы найти две функции, которые моделируют мои наблюдаемые времена выполнения (a, b, c, d, e, f - это константы, которые я уже нашел, но опущу):

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

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

где x - размер входного массива, а y - статистика заказа.

Теперь я немного заблудился от того, как использовать эти модели, чтобы вычислить, когда переключаться между квадратичной реализацией и линейной реализацией. Я подозреваю, что должен найти, где эти две функции пересекаются, но я не совсем уверен, как это сделать. Как найти, где эти две функции пересекаются?

Answer 1

В основном вы хотите использовать алгоритм с самой низкой оценкой времени выполнения.

Вы можете просто рассчитать значение каждого из предполагаемых времен выполнения и использовать алгоритм с наименьшим значением. Вы можете немного упростить это.

Вы хотите использовать четырехугольный алгоритм, когда:

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

Следовательно, вы можете вычислить ax + by -dexy + c-f и, если оно меньше нуля, использовать квадратичный алгоритм.