怠惰な評価の漸近複雑度

Question

厳密な評価では、評価されるべきサブ式と評価されるときの式が構文的に明らかであるため、プログラムの漸近的な複雑さを理由づけやすい。レイジー評価の言語ではそうではありません。式があるかどうか推測することは難しいと思う。O(n) , O(logn) or O(nlogn)

レイジー評価で漸近的複雑さに取り組む最も良い方法は何でしょうか？ わかりやすく説明できる人は大いに助けになるでしょう

Answer 1

厳密な評価では、計算コスト=使用コストです。

xs.map(cos)の場合は、cos *の長さ（xs）を支払う必要があります。

レイジー評価では、計算コストが<です。どのくらい具体的にそれが低いかは、計算の形に大きく依存します。

遅延評価の最も簡単な方法の1つは、ブール式の短絡です。 (x) => (cheap(x) || expensive(x))を見てください。

そのコストは、cheap(x)がどのくらいの頻度でtrueになるかによって大きく異なるため、expensive(x)は呼び出されません。同じことが他の遅延計算にも当てはまります。キャッシュ/メモの使用、ジェネレータの使用など。

big-Oのアプローチは、問題のサイズbig-Oについてです）、実際に実行される遅延計算の割合です。