algorithm - Prolog 程序的复杂性？

Question

在 Prolog 中，使用回溯来解决问题。它是一种声明性范例，而不是命令性范例（如 C、PHP 或 Python）。在这种语言中，是否值得考虑复杂性？

正如有人在这个问题中指出的那样，您认为问题的自然方式似乎是 O(N^2) 。

Answer 1

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

Answer 2

这完全取决于问题。

例如，据我所知，对数字列表求和是 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).

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

Answer 3

分析任何语言的复杂性很重要，无论是序言还是任何命令式语言。但是我可以给你一些提示来加快你的序言程序

1. 总是总是试图让你的程序尾递归。这将确保您的程序不会耗尽堆栈。
2. 尝试在您知道不需要任何进一步答案的程序中使用 cut and fail。
3. 尝试使用累加器。
4. 查看 CLPFD，它有助于大大减少搜索空间，从而加快您的程序。从本质上讲，它在您的程序可以回溯并浪费时间探索这些选择之前消除了错误的选择。
5. 始终首先编写最佳结果规则。（这真的取决于问题，但通常最好的情况规则是第一位的）。