Algoritmo de banca calculado complejidad de tiempo

Question

El algoritmo del banquero se utiliza para determinar si todas las solicitudes de recursos se pueden satisfacer sin llevar a un interbloqueo.

m es el número total de tipos de recursos

n es el número total de procesos

necesita es una matriz de tamaño m * n, se define solicitudes pendientes para cada tipo de recursos. E.g .: NEEDij = 2 significa que el proceso i está solicitando 2 elementos de recurso j.

El algoritmo es el siguiente:

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

Mi pregunta es, ¿cómo es tiempo de complejidad 0 (n * n * m)? Más específicamente, ¿cómo entra el m término en el polinomio? ¿Es porque tenemos que hacer una comparación elemento por elemento en un vector de longitud m?

Answer 1

Los parte presenta a continuación (n * m) Tiempo de complejidad

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

pero también se anida en un repetición bucle. Si ese ciclo puede ejecutarse, en el peor de los casos, n veces, entonces el procedimiento tiene una complejidad de tiempo O (n * n * m).

Actualización: me haya perdido algo,

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

Por lo tanto, el código que se ejecuta en el de bucle tiene O (m + m) complejidad del tiempo.
Por supuesto, O (m + m) = O (m) y la final complejidad es O (n * n * m).