3

我有一个递归：

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。我的问题是：第二个脚本运行的计算复杂度是多少，为什么？

4

1 回答 1

5

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

这是一个具体查询，它需要以指数方式进行许多推论：

?- 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 程序）通常比确定仅找到第一个答案的复杂性更容易。原因是前者与从句的精确顺序无关。不过，两者都取决于目标的顺序。

请参阅此答案以获取下限的理由。

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

于 2013-01-24T16:09:52.003 回答