Prolog程序的复杂性？

Question

在Prolog中，使用回溯来解决问题。这是一个声明式的范例，而不是一个命令式的范例（就像在C，PHP或Python中一样）。在这种语言中，是否值得从复杂性角度来思考？

您认为问题的自然方式似乎是O（N^2），正如有人指出this question。

Answer 1

它对于分析任何语言的复杂性非常重要，无论是序言还是任何命令式语言。不过，我可以给你一些提示，以加快你的prolog程序

1. 总是总是试图让你的程序尾递归。这将确保您的程序不会用完堆栈。
2. 尝试在你的程序中使用cut和fail，你知道你不需要任何进一步的答案。
3. 尝试使用准将。
4. 查看CLPFD，它有助于大幅缩小搜索空间，从而加快程序的运行速度。从本质上讲，它消除了在你的程序可以回溯并浪费时间探索这些选择之前的不良选择。
5. 总是先写出最好的结果规则。 （这真的取决于问题，但通常最好的情况下，规则首先）。

Answer 2

您可以像任何其他语言一样分析Prolog程序的复杂性。你链接的特定问题可能是O（n^2）。但并非所有的Prolog程序都会有这种复杂性。例如，您可以在Prolog中轻松编写SAT求解器，并且该问题是NP-Complete。

Answer 3

这完全取决于问题。

例如总结一个数字列表是O（N），据我所知。

sum([],0). 
sum(List,Total) :- 
    sum(List,0,Total). 

sum([],Total,Total). 
sum([Head|Rest],Accumulator,Total) :- 
    SoFar is Head + Accumulator, 
    sum(Rest,SoFar,Total). 

的唯一动作是在加入（“是”），并递归调用，它都应该是值得1每个。它们都会在列表中每个项目执行一次，因此总操作应该是〜2N，即O（N）。