地图降低复杂性

发布于 2024-10-09 17:49:02 字数 510 浏览 9 评论 0原文

假设我有这个输入：列表的列表

(def list-of-list-3 (列表 (列表 1 2 3) (列表 4 5 6) (列表 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)) ) 时间以线性方式增加，而不是二次增加。

谁能说出为什么？

提前致谢

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

安稳善良 2024-10-16 17:49:02

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

回复收藏 0 原文

≈。彩虹 2024-10-16 17:49:02

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

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

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

当我将输入大小[双倍]时
( list-of-list-6 (列表 (列表 1 2 3) (列表 4 5 6) (列表 7 8 9) 
                       (列表 8 2 3) (列表 9 8 1) (列表 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)) )

The map-reduce has a O(n^2) complexity in this case?

Impossible to say, unless you tell us what n corresponds to in the list-of-list-3 expression.

By the way, O(n^2) or O(n*n) is quadratic complexity, not exponential complexity. Exponential complexity it O(e^n).

when i [double] the input size
( 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)) )
the time increase in a linear way, not exponential.

From this, I surmise that the n is supposed to be the length of the outer list. If so, then the reduce is actually O(n) not O(n^2). To get quadratic growth, you would need to define list-of-list-6 as:

( 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)) )

回复收藏 0 原文

~没有更多了~