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程序)的复杂性,而不是确定仅找到第一个答案的复杂性.原因是前者与条款的确切顺序无关.但两者都取决于目标的顺序.

请参考这个答案以获得下限的理由.

编辑:也许最有趣的观察是:如果你想解决这个问题,那就是如果你想减少执行的推理数量,你必须改变失败切片可见部分的东西.