0
$\begingroup$

I have know that complexity of csp algorithms as follow:

Backtracking algorithm for constraint processing

space:O(n) ,Time :O(expn)

Backjumping algorithm for constraint satisfaction problem

space:0(n) ,Time :0(exp(logn w*))

Arc-Consistency algorithm-3(AC-3)

space:0(e),where e is the number of arcs and d is the size of largest domain
Time:0(ed^3)

Maintaining Arc-Consistency algorithm-3(MAC-3)

space:0(e+nd),where e is the number of arcs and d is the size of largest domain
time:0[ed^2+d*Σ c(c,x,a)]

Forward checking

time:0(d^n)

I don't know the time complexity of

Minimum remaining Value (MRV)
Least constraint value  (LCV)
FC_MRV
FC_LCV
AC3-BT
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.