Пересечение поверхности плоскостью
-
11-09-2019 - |
Вопрос
Я пытаюсь выяснить, когда алгоритм квадратичного выбора быстрее, чем алгоритм линейного выбора.Проведя несколько экспериментов, я создал два трехмерных графика, которые показывают время выполнения алгоритма в зависимости от размера входного массива и желаемой статистики порядка.Используя 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 — статистика порядка.
Теперь я немного не понимаю, как использовать эти модели для расчета, когда переключаться между квадратичной и линейной реализацией.Я подозреваю, что мне нужно найти место пересечения этих двух функций, но я не совсем уверен, как это сделать.Как найти место пересечения этих двух функций?
Решение
По сути, вы хотите использовать алгоритм с наименьшей оценкой времени выполнения.
Вы можете просто вычислить значение каждого из предполагаемых времен выполнения и использовать алгоритм с наименьшим значением.Вы можете немного упростить это.
Вы хотите использовать алгоритм 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
и если оно меньше нуля, используйте квадратичный алгоритм.