L'algorithme du banquier calcule la complexité temporelle

Question

L'algorithme du banquier est utilisé pour déterminer si toutes les demandes de ressources peuvent être satisfaites sans entraîner de blocage.

m est le nombre total de types de ressources

n est le nombre total de processus

besoin est une matrice de taille m * n, on définit les requêtes en attente pour chaque type de ressources. Par exemple: NEEDij = 2 signifie que le processus i demande 2 éléments de ressource j.

L'algorithme est donné ci-dessous:

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

Ma question est, comment est temps complexité 0 (n * n * m)? Plus précisément, comment le terme m entre-t-il dans le polynôme? Est-ce parce que nous devons faire une comparaison élément par élément sur un vecteur de longueur m?

Answer 1

La partie ci-dessous présente le (n * m) temps complexité

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

mais il est également niché dans une boucle de répétition . Si cette boucle peut s'exécuter, dans le pire des cas, n fois, alors la procédure a une complexité temporelle O (n * n * m).

Mise à jour: je raté quelque chose,

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

Ainsi, le code qui exécute dans la boucle for a O (m + m) la complexité du temps.
Bien sûr, O (m + m) = O (m) et la complexité finale est O (n * n * m).