バンカーのアルゴリズム計算時間の複雑度

Question

デッドロックに至らずにリソースのすべての要求を満たすことができるかどうかを判断するためにバンカーのアルゴリズムが使用されます。

mは、各リソースタイプの保留中の要求を定義し、

nは

必要がサイズm×n個のアレイであるプロセスの合計数であるリソースタイプの総数です。例：NEEDij = 2は、プロセスiが2つのリソースjを要求していることを示します。

アルゴリズムは以下の通りである：

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のベクトルに対して要素ごとの比較を行う必要があるからですか？

Answer 1

以下部紹介（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 

を逃し、 forループに実行されるコードはO（M + m）の時間複雑性を有します。もちろん、O（m + m）= O（m）であり、複雑さはO（n * n * m）である。