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文本的大小或复杂度将超过
任何特定的数据处理系统或语言的能力
处理器,还是相应的时候要采取的动作
超出限制;

永远记住,技术标准是确保系统适合某种目的的先决条件。 这不是一个充分的条件。 在这个答案中查看目的下面的例子是一个有点极端的例子。