弧一致性算法O（CD3）的复杂性为何？
最佳答案
我会判断你指的是AC-3一致性算法。
这个算法被很好地简单地描述为here。我将提到这个算法的描述。
首先，让我们计算方法的复杂性REVISE（方法修改两个域之间的一个弧）。对于一个域中的每个值，它将检查第二个域的所有值。因此，REVISE方法的复杂性将是D2，其中d is maximum domain size。
现在，最坏情况下，调用REVISE的次数是多少？最初，队列中有所有的弧。每次调用REVISE时，都会从队列中删除一个弧。这就是方法的e调用。但我们也在队列中添加弧。我们能做多少次？好吧，只有当一个值从arc所指向的域中删除时，我们才会将arc添加回队列。一个弧指向一个域，因此我们只能将其添加为该域中的值数目的倍。所以最坏的情况是，我们将每个弧都添加回队列d次。REVISE在最大的E+ED时间被调用，其中e is number of arcs。
当我们把它放在一起时，我们发现整个算法的复杂性是O（（E+ED）D2），它是O（ED3）。