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

分析任何语言的复杂性都很重要，无论是序言还是任何命令式语言。不过我可以给你一些技巧来加速你的 prolog 程序

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