2

我有一个在列表上工作的递归函数，该函数包含一个调用自身的循环，并以另一个函数结束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有人可以确认吗？

4

2 回答 2

1

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

令 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) 正如你所建议的。

我希望这是有帮助的。

于 2012-06-06T05:19:56.927 回答
1

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

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

  • 对于原始列表中的每个元素，构造一个少一个元素的新列表。这是等于n 2的总工作量
  • 一旦知道递归调用的结果，就将其添加到累加器中。这是等于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 < k < n）等等t ? (n) = Θ(n!)。

于 2012-06-08T08:31:31.640 回答