ISO Prolog谓词的复杂性
标准Prolog谓词的时间复杂度上限是否有保证？
例如：在任何符合标准的Prolog系统中，确定sort(+List, ?SortedList)在O（nlog（n））时间（n是List的长度）中运行？
tl; dr：不，不。
我们从sort/2开始，理想情况下需要nld（ n ）比较。 好，但是比较需要多长时间？ 让我们试试这个：
tails(Es0, [Es0|Ess]) :- Es0 = [_|Es], tails(Es, Ess). tails([],[[]]). call_time(G,T) :- statistics(runtime,[T0|_]), G, statistics(runtime,[T1|_]), T is T1 - T0. | ?- between(12,15,I), N is 2^I, length(L,N),maplist(=(a),L), tails(L,LT), call_time(sort(LT,LTs), Tms).
在SICStus 4.3.1和SWI 7.1.28上
I = 12, N = 4096, Tms_SICS = 680, Tms_SWI = 3332 I = 13, N = 8192, Tms_SICS = 2800, Tms_SWI = 14597 I = 14, N = 16384, Tms_SICS = 11300, Tms_SWI = 63656 I = 15, N = 32768, Tms_SICS = 45680, Tms_SWI = 315302
通过复制大小，我们可以轻松估计运行时间。 如果它重复，它是线性的，如果四倍是二次的。 显然，两者至less有二次方运行时。
以抽象的方式描述精确的运行时间可能是可能的，但要确保一切正常是非常困难的。 无论如何，要在标准文件中强制实现一个具体的承诺是不可能的。 而且，要validation这种说法是非常困难的。
最好的抽象度量可能是推论的数量，往往可以很容易地观察到。 查看最大的一个或多个整数 。 但是，这只是一个抽象的措施 – 所以有些东西被撕掉了， 抽象的 。 关键特征也可能被撕掉。
一般来说，ISO标准ISO / IEC 13211-1：1995的核心，并不要求任何明显超出范围的运行时复杂性的保证。 它在一个说明中明确提到资源限制也超出了范围：
1范围
….
注 – 本部分的ISO / IEC 13211没有规定：
a）Prolog文本的大小或复杂度将超过
任何特定的数据处理系统或语言的能力
处理器，还是相应的时候要采取的动作
超出限制;
…
永远记住，技术标准是确保系统适合某种目的的先决条件。 这不是一个充分的条件。 在这个答案中查看目的下面的例子是一个有点极端的例子。
