algorithm - 带循环的递归函数的复杂性

Question

我有一个在列表上工作的递归函数，该函数包含一个调用自身的循环，并以另一个函数g结束。其结构如下，为了简化问题，我们可以假设l始终是一个没有重复元素的列表。

let rec f l = function
  | [] -> g ()
  | _ ->
      List.fold_left
        (fun acc x ->
           let lr = List.filter (fun a -> (a <> x)) l in
           acc + (f lr))
        1 l

我不确定如何用 List.length l 和 g 的复杂度来表达这个函数的复杂度。

我认为它与g的复杂度和List.length l的阶乘成正比，有人能证实吗？

Answer 1

由于您假设列表 l 不包含任何重复项，因此此函数的作用是计算比原始列表少一个元素的所有子列表，并在所有子列表上递归调用自身。因此，当以 n 大小的列表开始时，调用 g 的次数为 g_?(n) = n · g_?(n-1) = n!

现在，让我们考虑该函数必须执行的其他所有操作。递归每一步的工作量包括:

• 对于原始列表中的每个元素，构造一个少一个元素的新列表。总工作量等于 n²
• 一旦知道递归调用的结果，请将其添加到累加器中。总工作量等于n(这部分可以忽略，因为过滤器的成本更高)。

因此，由于我们知道每个递归步骤将被调用多少次(基于我们之前的分析)，因此与 g 无关的工作总量为:t _?(n) = n² + n (n-1)² + n (n-1) (n-2)² + ... + n!

这个公式看起来很痛苦，但实际上 t_?(n)/n! 有一个有限的非零极限，即 n> 增加(它是 k+1/k! 与 0 < k < n 之和)，因此 t_? (n) = θ(n!).