내가 주어 졌어 재귀

Question

를 사용하여 배열에서 요소의 발생 횟수를 계산 다음과 같은 메시지

이 A을 나누어 v 배열 A 발생 횟수를 카운트 재귀 함수 만들기 매번 두 개의 서브 어레이로 나뉜다.

BinarySearch을 사용하는 것보다 더 좋은 방법은 무엇입니까? 나는 다음과 같은 기능을 만들어 :이 작동

int count(int *A, int low, int high, int v) { if(low > high) return 0; int total = 0, mid = (low + high)/2; if(A[mid] == v) total++; return count(A, low, mid - 1, v) + total + count(A, mid + 1, high, v); }

를, 그래서이 부분에 대한 검증이 필요하지 않습니다.

배열 A이 정렬되어 있는지 여부는 알 수 없으므로 배열 A의 왼쪽 절반과 오른쪽 절반을 모두 검색해야합니다. 하지만 필자가 작성한 함수의 시간 복잡성을 찾아야합니다. 다음은 내가 생각한 것입니다 :

모든 변수 지정은 O(1)이므로 고려해야 할 부분은 count(A, low, mid - 1, v) + total + count(A, mid + 1, high, v)입니다.

T(n) = T(n/2) + O(1) + T(n/2) = 2T(n/2) + O(1),

우리가 우리를 제공하기 위해 마스터 정리를 사용할 수 있습니다 우리가 2의 하위 문제의 크기 2 부분으로 배열을 분할하고 있기 때문에, 나는 다음과 같은 재발 관계를 만들었습니다 T(n) = O(n). 내 질문 : 변수 할당은 O(1)으로 일정하고 count 함수의 각 부분은 T(n/2)이 유효하다고 가정하고 있습니까?

배열의 모든 n 요소를 확인해야하기 때문에 전체 시간 복잡도는 O(n)입니다.

Answer 1

답안에 "예"라고 쓰고 답답한 답을 찾으십시오.

알고리즘 분석에서 가장 일반적으로 사용되는 계산 모델에서 더 많은 정보를 제공하기 위해 log(n) 비트를 포함하는 모든 연산은 O(1) 시간에 수행되는 것으로 가정합니다. 즉, 배열이 매우 크거나 (예 : 2^n) 값 자체가 매우 크지 않으면 모든 작업을 O(1) 시간 내에 수행 할 수 있다고 가정하는 것이 안전합니다.

T(n/2)에 관한 분석에서 각 재귀 호출에서 단순히 배열의 길이를 반으로 줄여 줘서 올바른 것 이외의 다른 말은 할 수 없습니다.