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）。