Complexité temporelle calculée de l'algorithme de Banker

Question

L'algorithme de Banker est utilisé pour déterminer si toutes les demandes de ressources peuvent être satisfaites sans conduire à une impasse.

m est le nombre total de types de ressources

n est le nombre total de processus

NEED est un tableau de taille m * n, qui définit les demandes en attente pour chaque type de ressources. Par exemple : NEEDij = 2 signifie que le processus i demande 2 éléments de la ressource j.

L'algorithme est présenté 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 la suivante : comment la complexité temporelle est-elle égale à 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 introduit une complexité temporelle de (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

mais il est également imbriqué dans un répéter boucle. Si cette boucle peut être exécutée, dans le pire des cas, n fois, la procédure a une complexité temporelle de O(n*n*m).

Mise à jour : J'ai raté quelque chose,

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

Ainsi, le code qui s'exécute dans le pour a une complexité temporelle de O(m+m).
Bien entendu, O(m+m) = O(m) et les final est O(n*n*m).