7

标准 Prolog 谓词的时间复杂度上限是否有任何保证？

例如：在任何符合标准的 Prolog 系统中是否确定sort(+List, ?SortedList)在 O(nlog(n)) 时间内运行（n 是 的长度）？List

4

1 回答 1

7

tl;博士：不，不。

让我们从sort/2理想情况下需要n ld( 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

通过复制大小，我们可以轻松估计运行时间。如果它也重复，它是线性的，如果它是四倍的，它是二次的。显然两者都至少具有二次运行时间。

以抽象的方式描述精确的运行时可能是可能的，但很难确保一切正常。在任何情况下，几乎不可能在标准文件中规定具体的承诺。此外，要验证此类声明非常困难。

最好的抽象度量可能是推论的数量，通常它们很容易观察到。查看最大的整数或因子。但同样，这只是一个抽象的措施——所以有些东西被撕掉了，抽象的。很可能关键功能也被撕掉了。

一般来说，ISO 标准 ISO/IEC 13211-1:1995 核心不要求对明显超出范围的运行时复杂性提供任何保证。它在注释中明确提到资源限制也超出了范围：

1 范围

……

注 — ISO/IEC 13211 的这一部分没有规定：

a) Prolog 文本的大小或复杂性将超过
任何特定数据处理系统或语言处理器的容量，或 超过相应限制
时要采取的措施； ...

永远记住，技术标准是确保系统适用于某些目的的先决条件。这不是充分条件。请参阅此答案中“目的”下的示例，以获取一些极端的示例。

于 2015-01-07T16:21:17.523 回答