计算函数式语言的 Big-O 时间和 space 复杂度

Question

我正在考虑将来使用 Ocaml 进行技术面试。但是，我不确定如何计算函数式语言的时间和 space 复杂度。 map、reduce 和 filter 等基本高级功能的基本运行时间是多少？通常如何计算运行时间和 space 复杂度？

Answer 1

持久递归实现的时间复杂度很容易直接从实现中推断出来。在这种情况下，递归定义直接映射到递归关系。考虑在标准库中实现的 List.map 函数：

let rec map f = function
  | [] -> []
  | a::l -> f a :: map f l

复杂度为 map(N) = 1 + map (N-1) 因此为 O(N)。

说到 space 复杂性，它并不总是那么明显，因为它需要了解尾调用和查看分配的技能。一般规则是，在 OCaml 中，本机整数、字符和不带参数的构造函数不会分配堆内存，其他所有内容都在堆中分配并装箱。所有非尾调用都会创建一个堆栈帧，从而消耗堆栈 space。在我们的例子中，堆栈域中 map 的复杂度是 O(N)，因为它进行了 N 次非尾调用。堆复杂度也是 O(N)，因为 :: 运算符被调用了 N 次。

另一个消耗space的地方是闭包。如果一个函数至少有一个自由变量（即一个未绑定到函数参数且不在全局范围内的变量），则创建一个称为闭包的函数对象，它包含一个指向代码的指针和一个指向每个自由变量（也称为捕获变量）。

例如，考虑以下函数：

 let rec rsum = function
   | [] -> 0
   | x :: xs -> 
     List.fold_left (fun y -> x + y) 0 xs + rsum xs

对于列表中的每个元素，此函数计算此元素与所有连续元素的总和。上面的简单实现是堆栈中的 O(N)（因为每个步骤都有两个非尾调用），堆大小中的 O(N)，因为每个步骤构造一个新的闭包（除非编译器足够聪明来优化它).最后在时域上是O(N^2)(rsum(N) = (N-1) + rsum(N-1))。

然而，它带来了一个问题——我们是否应该考虑计算产生的垃圾？即，那些在计算期间分配但未被其引用的值。或者像本例中那样仅在步骤中引用的那些值。所以这完全取决于您选择的计算模型。如果你会选择引用计数 GC，那么上面的例子在堆大小上肯定是 O(1)。

希望这会提供一些见解。如果有什么不清楚的地方，请随时提问。

计算函数式语言的 Big-O 时间和 space 复杂度

Calculating Big-O time and space complexity for functional languages

ocaml

functional-programming

runtime