tai*_*ion 4 complexity-theory haskell functional-programming higher-order-functions
映射和过滤器看起来像线性O(n),因为它们只需要遍历列表一次,但它们的复杂性是否受到传递的函数的影响？例如下面两个相同顺序的例子？
map (+) list
map (complex_function) list
你似乎有一个(常见的)误解,即复杂性是一个函数n.
什么是n？
n只是一个参数来衡量你的输入.它可能不足以(或甚至是必要的)统计数据来描述您的输入 - 您可能需要其他变量来准确描述输入的复杂性.
所以,map并且filter是线性的n.它们对其他变量的依赖取决于你传递的函数,但它们的依赖性n通常不会.
(脚注:是的,你可以传递一个函数,map并且filter在处理更多元素时实际执行更多的工作,但这是无趣的,除了我想在这里做的点.)
在几乎所有情况下,当高阶函数的文档表明其复杂性时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比较提供的列表中的两个元素.
然而,我不知道如何形式化和证明上述草拟的权利要求.很可能有一些关于这个主题的研究论文.
| 归档时间： |
|
| 查看次数： |
317 次 |
| 最近记录： |