银行家算法计算时间复杂度

Question

Banker的算法用于确定是否可以满足所有资源请求而不会导致死锁.

m是资源类型的总数

n是进程总数

NEED是一个大小为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).