시간 복잡도 점화식

Question

내가 재발 관계를 찾을 필요가

:

int search(int[] a, int l, int h, int goal) { 
    if (low == high) return 0; 
    int tg = target(a, l, h); 
    if (goal < target) 
     return search(a, l, tg-1, goal); 
    else if (goal > target) 
     return search(a, tg +1, h, goal); 
    else 
     return a[tg]; 
} 

무엇이 문제에 접근하는 초기 방법이 있을까요? 나는 해결책을 요구하는 것이 아니라 접근하는 초기 방법 일 뿐이다. 감사!

Answer 1

정확한 해결책을 묻지 않으므로 (원하는 경우 제공 할 수 있음) 나는 매우 간단하지만 잘 알려지지 않은 접근 방법에 대한 힌트를 제공 할 것입니다. 그런 문제.

결정적인 아이디어는 아마도 최악의 복잡성을이 함수에 함수를 수정하는 것입니다,하지만 예상 복잡성의이 수정 기능 findTarget2 부르 자, 쉽게 측정 할 수 있습니다 f(n)하자, 이제

public static int findTarget2 (int[] a, int low, int high, int goal) { 
    if (low == high) return 0; 
    int len = high - low + 1; //length of the array range, i.e. input size 
    while (true) { 
     int target = selectTarget(a, low, high); 
     if (goal < target && target-low <= 3/4 * len) 
      return findTarget2(a, low, target-1, goal); 
     else if (goal > target && high-target <= 3/4 * len) 
      return findTarget2(a, target+1, high, goal); 
     else if (goal == target) 
      return a[target]; 
    } 

} 

을 원래의 시간 복잡도이고 g(n)은 findTarget2 함수의 시간 복잡도이며, n은 입력 크기, 즉 high-low+1과 같은 배열 범위의 길이입니다.

자, selectTarget이 불량 실행으로 표시되는 경우 만 본인의 신체에 반품 전화가 발생하지 않는 경우에만 해당한다고 가정 해 봅시다.

잘못된 실행의 경우 findTarget2은 기본적으로 동일한 입력에서 자체 호출을 수행하지만 원본 함수는 입력 크기를 1 이상 줄이므로 첫 번째 결과는 g(n) >= f(n)입니다. 따라서 상한값 g(n)의 경우 동일한 범위가 f(n)에 적용됩니다. 다음

다음, g(n) 예상 시간 복잡도가 기록 될 수있다 :

예상 값을 사용하여 직선은 다음과 같이 쓸 수

EX[g(n)] <= EX[g(3/4 * n) + X * O(n)] 

:

EX[g(n)] <= EX[g(3/4 * n)] + EX[X] * O(n) 

X 랜덤 변수이고 return 호출이 발생할 때까지 while 루프 실행 횟수를 나타내며, 마지막으로 O(n)은 findTarget2 함수에서 보낸 비 재귀 시간이며,입니다. 210, 왜냐하면 그 시간에 selectTarget 함수가 실행된다고 말하기 때문입니다.

지금 당신의 작업은 EX[X]을 계산 한 다음도 f(n)의 예상 시간 복잡도에 대한 상한이다 g(n)의 최종 예상 시간 복잡도를 얻을 수 Master theorem를 사용할 수 있으므로의 복잡성의 상한이다 원래 함수.