scheme - スキームの acc 関数の時間計算量は?

Question

引数の 1 つだけに関して、この関数の厳密にバインドされた時間の複雑さを見つけようとしています。私はそれが O(p^2) (またはかなり大きなシータ) だと思っていましたが、もうわかりません。

(define (acc p n)
  (define (iter p n result)
    (if (< p 1) 
        result
        (iter (/ p 2) (- n 1) (+ result n))))
  (iter p n 1))

Answer 1

@sarahamedani、なぜこれは O(p^2) になるのでしょうか? 私には O(log p) のように見えます。ランタイムは の値に影響されないようにする必要がありますn。

からカウントダウンして、一連の数値を合計していnます。反復回数は、1 未満にならずに半分にできるiter回数に依存します。つまり、 の左端の「1」ビットの位置から 1 を引いたものが、反復回数です。つまり、実行回数は に比例します。ppiteriterlog p

Answer 2

あなたはそれを目で見てみるか、より体系的にそれから行くかもしれません。これを最初から行っていると仮定すると、関数定義から漸化式を構築してみる必要があります。

今のところ、算術演算と変数ルックアップが一定時間である非常に単純なマシンモデルを想定できます。

の終了は。にのみ依存するため、計算に必要なステップ数をカウントする関数の名前とし、それをの関数としiter-costます。そうすれば、の式を書くことができるはずです。、、、、およびに対してそれを行うことができますか？iterpiterpiter-cost(0)iter-cost(1)iter-cost(2)iter-cost(3)iter-cost(4)

より一般的には、pゼロより大きい場合、表現できますiter-cost(p)か？これは、定数とへの繰り返しの呼び出しの観点から行われiter-costます。あなたがそれを再発として表現することができれば、あなたはそれを閉じた形で表現するためのより良い立場にいます。