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

Question

银行家算法用于确定是否可以满足所有资源请求而不会导致死锁。

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的向量进行逐个元素比较吗？

- Natalia

---

根据您对我的刚刚被删除的答案的评论，这段代码中的含义真的很不清楚。NEEDi、ALLOCATION_i是什么？在内部是逐元素分配工作还是其他方式？这段代码来自哪里？ - sharptooth

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）。

- Nick Dandoulakis

---

所以m是因为在大小为m的向量上进行了<=操作吗？ - Natalia

是的，那个搜索/比较会额外增加O(m)的时间成本。 - Nick Dandoulakis