私は、引数のうちの1つだけに関して、この関数の厳密な境界時間の複雑さを見出そうとしていました。私はそれがO（p^2）（またはむしろ大きなシータ）だと思ったが、私はもはや確信していない。スキームのacc関数の時間複雑度は？
(define (acc p n)
(define (iter p n result)
(if (< p 1)
result
(iter (/ p 2) (- n 1) (+ result n))))
(iter p n 1))
@ sarahamedani、なぜこれはO（p^2）ですか？私にはO（log p）のように見えます。ランタイムはnの値に影響されません。
nから数えて、一連の数字を合計しています。 iterの回数は、pが1未満にならずに半分になることができる回数に依存します。つまり、pの最も左の '1'ビットの位置から1を引いた数値は、iterの繰り返し回数になります。つまり、iterの実行回数はlog pに比例します。
あなたは眼球を試してみるか、体系的に眼球を試してみてください。これを最初からやっていると仮定して、関数定義から反復関係を構築しようとする必要があります。
ここでは、算術演算と変数検索が一定時間である非常に単純な機械モデルを仮定することができます。
はiter-costは、それがiterを計算し、iterの終了のみpに依存しているため、それは、pの関数とするのにかかるどのように多くのステップをカウントする関数の名前とします。次に、iter-cost(0)の式を書くことができるはずです。 iter-cost(1)、iter-cost(2)、iter-cost(3)、およびiter-cost(4)についてそれを行うことはできますか？ゼロより大きいp与え
は、あなたがiter-cost(p)表現することができますか？それは定数の点で、iter-costへの再帰呼び出しになります。あなたが再発としてそれを表現することができれば、閉じた形で表現するのがより良い立場にあります。
ちょうどペナントであるために、それは純粋に技術的な定義から話すプログラム集合O（p^2）にあります。それはもっと小さな集合にも属しているというだけで、O（p^2）が上境界をあまりにも緩い方法であることをOPに説得しようとしています。 – dyoo