Thuật toán của ngân hàng tính toán độ phức tạp thời gian

Question

Thuật toán của Ngân hàng được sử dụng để xác định xem tất cả các yêu cầu về tài nguyên có thể được đáp ứng mà không dẫn đến bế tắc hay không.

m là tổng số các loại nguồn lực

n là tổng số của các quá trình

CẦN là một mảng có kích thước m * n, nó định nghĩa đề nghị.Nhấn đối với từng loại tài nguyên. Ví dụ: NEEDij = 2 có nghĩa là quá trình tôi đang yêu cầu 2 mục tài nguyên j.

Các thuật toán được đưa ra dưới đây:

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)); 
} 

Câu hỏi của tôi là, làm thế nào là thời gian phức tạp 0 (n * n * m)? Cụ thể hơn, thuật ngữ m nhập vào đa thức như thế nào? Có phải vì chúng ta phải so sánh từng phần tử trên một vectơ có chiều dài m không?

Answer 1

giới thiệu phần bên dưới (n * m) thời gian phức tạp

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

nhưng nó cũng được lồng trong một lặp lại vòng lặp. Nếu vòng lặp đó có thể chạy, trong trường hợp xấu nhất, n lần, thì thủ tục có độ phức tạp thời gian O (n * n * m).

Cập nhật: tôi đã bỏ lỡ một cái gì đó,

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

Vì vậy, các mã thực thi trong cho vòng lặp có O (m + m) thời gian phức tạp.
Tất nhiên, O (m + m) = O (m) và cuối cùng là độ phức tạp là O (n * n * m).