haskell - 高阶函数的计算复杂性？

Question

Map 和 filter 看起来像是线性 O(n)，因为它们只需要遍历列表一次，但是它们的复杂性是否受到传递的函数的影响？例如下面的两个例子是同一个顺序吗？

map (+) list

map (complex_function) list

Answer 1

几乎在所有情况下，当高阶函数的文档说明其复杂度为 O(f(n)) 时， ，这是假设高阶函数具有恒定的时间复杂度 O(1) 。进一步来说，n的确切含义可能会有所不同，但如果没有明确说明，则应从上下文中清楚地看出:例如列表的长度、集合/映射中元素/关联的数量等等。

假设我们有一个高阶函数 g称为 g h ...哪里h是一个函数，...是一阶数据。没有关于高阶函数的任何其他信息g ，如果文档指出它是 O(f(n)) ，您可以获得更现实的最坏情况界限 O(f(n)) * CostH哪里CostH代表调用 H 的费用一次。

当然，CostH还取决于哪些参数开始传递给 h :在这里，我们所知道的是这些参数是在 O(f(n)) 中构建的时间。很难获得 h 参数大小的有用的一般界限。因为，例如，如果 h以树作为输入，那么你可以在短时间内构建一棵非常大的树:

foo :: Int -> Tree ()
foo 0 = Tree []
foo m = Tree [t,t] where t = foo (m-1)

上面构建了一棵具有 2^m 的树离开 m时间(感谢分享)。这个可以修改为3^m或发送至b^m琐碎地保留b*m复杂性。

但是，可能有某种方法可以利用参数性来恢复更有用的界限。例如，如果我们的订单函数具有类型

g :: (a -> Int) -> [a] -> Int

然后我们知道 g h [...]只能调用h参数取自列表。同样，库函数调用sortBy h [...]只能使用h比较所提供列表中的两个元素。

然而，我不知道如何形式化和证明上面概述的主张。很可能有一些关于该主题的研究论文。