私がこの関数を持っているとしましょう:(Haskell構文)
f x = (x,x)
関数によって実行される作業(計算量)は何ですか?
最初は明らかに一定だと思っていましたが、タイプがx
有限でない場合、つまりxが任意の量のメモリを使用できる場合はどうでしょうか。コピーによって行われる作業も考慮に入れる必要がありx
ますよね?
これにより、関数によって実行される作業は、実際には入力のサイズで線形であると私は信じました。
これはそれ自体が宿題ではありませんが、関数によって実行される作業を定義する必要があるときに思いついたものです。
f x = [x]
同様の問題があると私は信じています。