0

この歩数の問題について質問があります。私は基本的な考えを持っていると思いますが、数学を紙にまっすぐにするのに苦労しています。最初に擬似コード：

for i = 1 to n
    x = x + 1
    j = n
    while (j>1)
        j = j/2

と私の解釈：

n / 2 + 1

n / 2

n / 2

n / 2 <-4行目の合計の上部（whileループ）

Σlogn+2

i = 1 <-4行目の合計の下部（whileループ）

n / 2 <-5行目の合計の上部（whileループの本体）

Σlogn+1

i = 1 <-5行目の合計の下部（whileループの本体）

したがって、ステップ数の最初の3行は見た目が悪くありませんが、ループ内の2つの合計は少し注意が必要です。したがって、最初の1つのlogn + 2については、2つのステップに分割できます。

n / 2

Σ2

i = 1

と

n / 2

Σlogn

i = 1

だから私はn/2ではなくnの直線和を扱うことに慣れています。しかし、私はそれに簡単なショットを与えます。

2 *（（n ^ 2 + n）/ 2）または、この分数をドロップして、まっすぐにします：n ^ 2+n。

次に、lognピースの場合：

logn *（（n ^ 2 + n）/ 2）=？今、私はここで本当によくわかりません。これがまったく単純化するかどうかさえわかりません。誰かがこれについて何か提案があれば私はそれを感謝します、しかし私がそこに得たものはこの半分のためのものだと思います。したがって、2つを組み合わせて、擬似コードの最初の合計4行目の最終的な答えを取得します。

logn *（n ^ 2 + n）/ 2 + n ^ 2 + n

そして、2回目の合計では、次のようになると思います。

logn * n ^ 2 + n

（上記ですでに完了したものから少し借りることができます。2*（n ^ 2 + n）/ 2の部分を削除するだけで、代わりに2セットの半分を組み合わせて1つのn^を作成します。 2 + nそれが理にかなっているとしたら？

完全に紛失した場合はお知らせください。ありがとうございました！！

4

1 に答える 1

0

あなたの分析は少しずれていると思います。まず、forループの本体で発生することは、iまたはの値とは無関係であることに注意してくださいx。したがって、forループは何度も実行され、ループ本体で毎回n同じ数のステップが発生します。forループの本体whileは floor(log 2 (n)) 回実行されます。必要な分析はこれだけです。結果は n*floor(log 2 (n)) です。(「ステップ」がステートメントの実行を意味する場合は、各ループ本体のステートメントの数を考慮して、これを少し変更する必要があります。)

于 2012-11-18T09:04:18.680 に答える