Bankalgorithmus berechnete Zeitkomplexität

Question

Der Banker-Algorithmus wird verwendet, um zu bestimmen, ob alle Anforderungen für Ressourcen erfüllt werden können, ohne zu einem Deadlock zu führen.

m ist die Gesamtanzahl der Ressourcen-Typen

n die Gesamtzahl der Prozesse

müssen, ist ein Array von m * n Größe, es definiert Anforderungen für jeden Ressourcentyp anhängig. Beispiel: NEEDij = 2 bedeutet, dass der Prozess i zwei Ressourcenelemente anfordert.

Der Algorithmus ist unten angegeben:

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

Meine Frage ist, wie ist Zeit Komplexität 0 (n * n * m)? Genauer gesagt, wie tritt der m-Term in das Polynom ein? Liegt es daran, dass wir einen Element-für-Element-Vergleich auf einem Vektor der Länge m durchführen müssen?

Answer 1

Die nachfolgende Teil wird (n * m) Zeitkomplexität

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

aber es wird auch in einem Wiederholungs Schleife verschachtelt. Wenn diese Schleife im schlimmsten Fall n mal durchlaufen kann, dann hat die Prozedur eine O (n * n * m) Zeitkomplexität.

Update: ich etwas verpaßt,

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

der Code also, die in den für Schleife ausgeführt hat O (m + m) Zeitkomplexität.
Natürlich ist O (m + m) = O (m) und die endgültige Komplexität ist O (n * n * m).