prolog - 序言中递归的计算复杂性

Question

我有一个递归:

list_to_set([],[]).

list_to_set([A|X],[A|Y]):-
   list_to_set(X,Y),
    \+member(A,Y).

list_to_set([A|X],Y):-
   list_to_set(X,Y),
   member(A,Y).

它将元素列表转换为集合。例如 [1,1,2,3] -> [1,2,3]。当我输入查询 list_to_set([1,1,2,3],X). 时，结果是 X = (1,2,3) 并且复杂度为找出集合是 O(n)。现在我可以输入 ; 来确定没有其他可能的答案。显然没有，脚本将返回 false。我的问题是:第二个脚本运行的计算复杂度是多少，为什么？

Answer 1

对于您的程序，找到第一个答案在最坏的情况下是指数级的。在最好的情况下它是二次的。

这是一个具体的查询，它采用了指数级的许多推理:

?- length(L,N),maplist(=(a),L),time(once(list_to_set(L,S))).
   ...
;  % 1,310,714 inferences, 0.180 CPU in 0.180 seconds (100% CPU, 7288089 Lips)
   L = [a,a,a,a,a,a,a,a,a|...], N = 18, S = [a]
;  % 2,621,434 inferences, 0.337 CPU in 0.337 seconds (100% CPU, 7789752 Lips)
   L = [a,a,a,a,a,a,a,a,a|...], N = 19, S = [a]
; ... .

确定 Goal, false 的复杂性(假设程序本质上是纯 Prolog 程序)通常比确定仅找到第一个答案的复杂性更容易。原因是前者与从句的精确顺序无关。不过，两者都取决于目标的顺序。

请引用this answer下限的理由。

编辑:也许最有趣的观察是这样的:如果你想解决这个问题，也就是说，如果你想减少执行的推理次数，你必须改变失败切片的可见部分。