1

让我们假设我有这个输入：列表列表

(def list-of-list-3 (list (list 1 2 3) (list 4 5 6) (list 7 8 9))

(map #(reduce * %1) list-of-list3 )

在这种情况下，map-reduce 的复杂度为 O(n^2)？

map-reduce 被翻译成两个嵌套的 for 吗？

因此，当我在 clojure REPL 上运行上述示例时，复杂度时间看起来像 O(n)。

当我复制输入大小时（ list-of-list-6 (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 8 2 3) (list 9 8 1) (list 7 6 4)) ) 时间以线性方式增加，而不是二次增加。

谁能说出为什么？

提前致谢

4

2 回答 2

4

这不是 O(n^2)，它大约是 O(n*m)，其中 n 是列表的数量，m 是它们的长度。还有其他因素与各种数字的长度有关。用手做，自己计时，看看为什么！

于 2010-12-28T12:05:30.693 回答
2

在这种情况下，map-reduce 有O(n^2)复杂性吗？

不可能说，除非您告诉我们表达式n中对应的内容。list-of-list-3

顺便说一下，O(n^2)orO(n*n)是二次复杂度，而不是指数复杂度。指数复杂度吧O(e^n)。

当我 [加倍] 输入大小时

( list-of-list-6 (list (list 1 2 3) (list 4 5 6) ( list 7 8 9) 
                       (list 8 2 3) (list 9 8 1) (list 7 6 4)) )

时间以线性方式增加，而不是指数增加。

由此，我推测n应该是外部列表的长度。如果是这样，那么reduce实际上O(n)不是O(n^2)。要获得二次增长，您需要定义list-of-list-6为：

( list-of-list-6 (list (list 1 2 3 4 5 6) (list 4 5 6 1 3 2) 
                       (list 7 8 9 1 2 3) (list 8 2 3 2 3 4) 
                       (list 9 8 1 2 3 4) (list 7 6 4 5 6 7)) )
于 2010-12-28T12:10:16.903 回答