귀속 행위 시간 복잡도
1070 단어 알고리즘과 데이터 구조
그 중에서 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)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Python3를 사용하여 빠른 배열 정렬2020년 새해 복 많이 받으세요.저는 ryuichi69라고 합니다.오늘도 알고리즘 연습의 성과, 연습을 설명하는 동시에 이 글을 썼다.솔직히 이해하기 쉽게 쓰느라 힘들었는데 설명하기 어려운 부분, 요건 누락 등이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.