待ち行列による根拠の計算

次の算法を考える。

各 $s \in P$ について計数 $c[s]$ を $|\mathrm{prem}(s)|$ で初期化し、各 $u \in N$ について、$u$ を前提にもつ $s \in P$ の一覧 $\mathrm{users}[u]$ を作る。集合 $G$ を $B \cup \{s \in P : c[s] = 0\}$ で初期化し、$G$ の元をすべて待ち行列に入れる。待ち行列が空でないかぎり、$u$ を 1 つ取り出し、$\mathrm{users}[u]$ の各 $s$ について $c[s]$ を $1$ 減らし、$0$ になったら $s$ を $G$ に加えて待ち行列に入れる。

この算法は止まり、止まったとき $G = \mathrm{Gr}(K)$ である。依存の総数を $M = \sum_{s \in P} |\mathrm{prem}(s)|$ とすると、計算時間は $O(|N| + M)$ である（定義 3.1［計算量と O 記法］）。