은행가 알고리즘 계산 시간 복잡도

은행가 알고리즘은 교착 상태가 발생하지 않고 리소스에 대한 모든 요청을 충족시킬 수 있는지를 결정하는 데 사용됩니다.은행가 알고리즘 계산 시간 복잡도

m은 각 자원 타입 보류 요청을 정의

n은

필요 M 사이즈 * n의 배열 인 프로세스의 총 개수 자원 유형의 총 개수이다. 예 : NEEDij = 2는 프로세스 i가 리소스 2 개 항목을 요청하고 있음을 나타냅니다.

알고리즘은 아래에 주어진다 :

BOOLEAN function SAFESTATE is -- Determines if current state is safe 
{ NOCHANGE : boolean; 
    WORK : array[1..m] of INTEGER = AVAILABLE; 
    FINISH : array[1..n] of boolean = [false, ..,false]; 
    I : integer; 

    repeat 
    NOCHANGE = TRUE; 
    for I = 1 to N do 
     if ((not FINISH[i]) and 
     NEEDi <= WORK) then { 
     WORK = WORK + ALLOCATION_i; 
     FINISH[i] = true; 
     NOCHANGE = false; 
     } 
    until NOCHANGE; 
    return (FINISH == (true, .., true)); 
}

질문이다 어떻게 시간 복잡도 0 (N *의 n 개의 *의 m)? 더 구체적으로, m 항은 다항식을 어떻게 입력합니까? 그것은 길이 m의 벡터에 대해 원소 별 비교를해야하기 때문입니까?

출처

2009-08-19 Anonymous

방금 삭제 한 답변에 대한 귀하의 의견과 함께이 코드에서 의미하는 것이 무엇인지 분명하지 않습니다. NEEDi, ALLOCATION_i는 무엇이며 WORK는 요소별로 또는 요소별로 할당되는 방법은 무엇입니까? 이 코드의 출처는 어디입니까? – sharptooth

아래 부분 컨덕터 (N *에서의 m) 시간 복잡도

for I = 1 to N do // *n times 
     if ((not FINISH[i]) and 
     NEEDi <= WORK) then // *m times, if it's an array search

이 있지만 또한 반복 루프에 중첩된다. 그 루프가 최악의 경우, n 번 실행될 수 있다면, 절차는 O (n * n * m) 시간의 복잡성을 갖습니다.

업데이트 : 내가 뭔가를 놓친,

WORK = WORK + ALLOCATION_i; // also O(m) operation, vectors addition

그래서, 루프의 에서 실행 코드가 O (m의 + 분) 시간 복잡도가 있습니다. 물론, O (m + m) = O (m) 및 복잡도는 O (n * n * m)이다.

출처

2009-08-19 07:49:57

그래서 크기 m의 벡터에서 <= 연산 때문에 m이 있습니까? –

예, 검색/비교에는 추가 O (m) 시간 비용이 있습니다. –

@Natalia, 내 업데이트를 참조하십시오. –

은행가 알고리즘 계산 ​​시간 복잡도

답변

관련 문제

은행가 알고리즘 계산 시간 복잡도