问惰性计算的渐近复杂性
EN

Stack Overflow用户

提问于 2017-07-08 14:23:00

回答 1查看 45关注 0票数 0

在严格的计算中，更容易推断出程序的渐近复杂性，因为要计算的子表达式和何时计算的子表达式在语法上是显而易见的。这不是懒惰计算语言的情况。我发现很难推测一个表达式是否是O(n) , O(logn) or O(nlogn)

使用惰性评估解决渐近复杂性的最佳方法是什么？如果有人能解释给我听会很有帮助。

发布于 2017-07-08 15:14:13

有了严格的评估，计算成本=使用成本。

如果使用xs.map(cos)，则需要支付cos * length(xs)的成本。

使用惰性评估，使用成本<计算成本。具体来说，它有多低，很大程度上取决于计算的形状。

惰性计算的最简单形式之一是布尔表达式的短路。看看(x) => (cheap(x) || expensive(x))吧。

它的计算成本很大程度上取决于cheap(x)为真的频率，因此expensive(x)不会被调用。这同样适用于其他惰性计算，例如使用缓存/内存，使用生成器等。

在我看来，大O方法并不适用于这样的问题，除非你能在问题的大小(这就是大O)和实际执行的懒惰计算速率之间找到一个明确的依赖关系。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/44983200

复制

相似问题

问惰性计算的渐近复杂性EN