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!).