具有循环的递归函数的复杂性

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 2 + n （n-1）2 + n （n-1） （n-2）2 + ... + n！

这个公式看起来很痛苦，但实际上t_？（n）/n！随着 n 的增加，具有有限的非零极限（它是 k+1/k！ 与 0 的总和）等等 t_？（n） = Θ（n！）。

Answer 2

好的。 我不是故意要显得不信任。这确实看起来像一个函数式编程作业，因为它不是很实用的代码。

设 F（n） 为长度为 n 的输入的比较数加上加法数。并让 G 成为 g 的运行时间。 由于 g 不接受任何操作数，因此 G 是常数。我们只是在计算它的调用次数。

折叠将执行其功能 n 次。 每次执行都会调用 filter 进行 n 次比较，每次从其输入中只删除一个元素，然后递归调用此缩短列表上的 f 并执行一次加法。 所以总成本是

F（n） = n * （n + F（n - 1） + 1） [ 如果 n> 0 ] = G [ 否则 ]

第一个术语扩展到

F（n） = n * F（n - 1） + n^2 + n

这是你提议的O（n！ + n^3 + n^2 + nG） = O（n！ + nG）。

我希望这是有帮助的。