0

次のアルゴリズムを検討してください。

i := 1
t := 0
    while i ≤ n
       t := t + i
       i := 2i

このアルゴリズムが実行する加算演算と乗算演算の数を調べることに興味があります。しかし、私は困っています。i の値が反復ごとに 2 倍になることは理解していますが、アルゴリズムを一般化して n の値までの正しい数の演算を与える方法がわかりません。誰かがこの問題に光を当てることができれば、私はそれを大いに感謝します.

ありがとうございました！

4

1 に答える 1

1

doublesの値はiループごとにi <= n

i*2^x <= n

x を最大化すると、ループの数が得られます。i = 1 なので

2^x = n
x = floor log(n)

ループごとに 1 回の加算と 1 回の乗算を実行します。私はあなたがここからそれを取ることができると思います:)

于 2012-12-05T06:12:09.167 に答える