표면의 교차점

Question

2 차 선택 알고리즘이 선형 선택 알고리즘보다 빠른시기를 알아 내려고합니다. 일부 실험을 실행하면 알고리즘 실행 시간을 입력 배열 크기의 함수 및 원하는 차수 통계의 함수로 표시하는 두 개의 3D 플롯을 생성했습니다. GnuPlot을 사용하여 플롯을 그려서 2 차 알고리즘이 더 빠른 경우가 있음을 확인했습니다. 그런 다음 Gnuplot의 피팅 알고리즘을 사용하여 관찰 된 런타임 (A, B, C, D, E, F를 모델링하는 두 가지 기능을 찾았습니다.

lin_alg_runtime (x, y) = ax + by +c

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

여기서 x는 입력 배열의 크기이고 y는 주문 통계입니다.

이제 저는 이러한 모델을 사용하여 2 차 구현과 선형 구현 사이를 전환 할시기를 계산하는 방법에 대해 잃어 버렸습니다. 나는이 두 기능이 어디에서 교차하는지 찾아야한다고 생각하지만 어떻게 해야할지 잘 모르겠습니다. 이 두 기능이 어디에서 교차하는지 어떻게 찾습니까?

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 0보다 작은 경우 2 차 알고리즘을 사용하십시오.