다음 알고리즘의 반복 관계 란 무엇입니까?

다음의 회귀 관계는 T (n) = T (n-1) + 2 + T (n + 1)입니까?
모든 if 문이 다른 문을 제외하고 있기 때문에 중간 변수 할당과 마지막 행을 계산합니다 ...이 접근법이 맞습니까?다음 알고리즘의 반복 관계 란 무엇입니까?

/* 
* V is sorted 
* V.size() = N 
* The function is initially called as searchNumOccurrence(V, k, 0, N-1) 
*/ 
int searchNumOccurrence(vector<int> &V, int k, int start, int end) { 
    if (start > end) return 0; 
    int mid = (start + end)/2; 
    if (V[mid] < k) return searchNumOccurrence(V, k, mid + 1, end); 
    if (V[mid] > k) return searchNumOccurrence(V, k, start, mid - 1); 
    return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end); 
}

출처

2017-05-09 marcoshass

이진 검색입니까? – Cameron

[이진 검색] (https://en.wikipedia.org/wiki/Binary_search_algorithm)과 유사합니다. 특정 값을 갖는 요소의 수를 계산하기 위해 하나의 일치하는 요소가 발견되면 주변 요소를 스캔 할 수 있다고 생각합니다. – ilkkachu

복잡성은 당신이 언급 한 것이 아닙니다. 그것은 T (n) = 2 * T (n/2) + c이다. –

의견에 @GAURANG VYAS가 언급했듯이. 반복 관계는 T (n) = 2 * T (n/2) + O (1)이고 Theta (n)이다. Binary Search은 O (log n)이고 그 반복 관계는 T (n) = T (n/2) + O (1)

이 될 것입니다. searchNumOccurrence() 방법은 주어진 k의 모든 발생을 조회하므로 V의 모든 원소가 k와 같은 경우 정준 예.

출처

2017-05-09 20:14:23 gue

다음 알고리즘의 반복 관계 란 무엇입니까?

답변

관련 문제