懶惰評估的漸近複雜性

Question

在嚴格評估中，更容易推理程序的漸近複雜性，因爲由於將評估的子表達式以及評估時的子表達式在語法上是明顯的。懶惰評估的語言並非如此。我發現很難推測是否表達式是O(n) , O(logn) or O(nlogn)

用懶惰評估解決漸近複雜性的最佳方法是什麼？ 有人可以爲我解釋明白會很有幫助

Answer 1

有嚴格的評估，計算成本=使用成本。

如果你做xs.map(cos)，你需要支付cos *長度（xs）的費用。

用懶惰評估，使用成本<計算成本。它具體如何更低，很大程度上取決於計算的形狀。

懶惰評估的最簡單形式之一是布爾表達式的短路。看看(x) => (cheap(x) || expensive(x))。

它的計算成本很大程度上取決於cheap(x)的真實性，因此不會調用expensive(x)。同樣適用於其他懶惰計算，例如使用緩存/記憶，使用發電機等。

在我看來，大O方法不適用於這樣的問題，除非你能找到問題的大小之間的明確依賴關係大O大約）以及實際執行延遲計算的比率。