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

Question

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

lin_alg_runtime(x,y) = ах + бу +с

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

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

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

Answer 1

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

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

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

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 и если оно меньше нуля, используйте квадратичный алгоритм.