귀속 행위 시간 복잡도

master 공식의 사용: T(N) = a*T(N/b) + O(n^d)
그 중에서 N은 행위의 총 샘플 양이고 N/b는 하위 행위의 샘플 양이며 a는 하위 행위가 발생하는 횟수이며 하위 프로세스를 호출하는 것을 제외하고 나머지 조작을 하는 데 걸리는 시간 대가이다.
단순 귀속 코드:
//   
function getMax(arr,L,R){
    if(L==R){
        return arr[L];
    }
    var mid = (L+R)/2;
    var max_left = getMax(arr,L,mid);
    var max_right = getMax(arr,mid+1,R);
    return Math.max(max_left,max_right);
}

상기 코드 중 a는 2, b는 2이고 추가 조작의 시간 복잡도는 O(1), 즉 d=0
a, b, d와 시간 복잡도 O의 관계: 1) log(b, a) > d 복잡도 O (N^log(b, a) 2) log(b, a) = d 복잡도 O (N^d * logN) 3) log(b, a) < d 복잡도 O (N^d)

좋은 웹페이지 즐겨찾기