2

あなたが私がパートaをするのを手伝ってくれるなら、私はおそらくパートbを理解することができます。私はこれと同様の問題を一日中見てきましたが、ネストされたループをどうするかを理解するのに問題があります。最初のループにはn回の反復があり、2番目のループにはn-1があり、3番目のループにはn-1があります。これについて正しく考えていますか？

次のアルゴリズムを考えてみましょう。
これは、n個の整数a1、a2、...、anのシーケンスを入力として受け取り、
出力として行列M = {mij}を生成します。ここで、mijは 整数ai、a+1のシーケンスの
最小項です。
、...、aj for j>=iおよびmij=0それ以外の場合。

j>=iおよびmij=0の場合、mij=aiとなるようにMを初期化します。

for i:=1 to n do
    for j:=i+1 to n do
        for k:=i+1 to j do
            m[i][j] := min(m[i][j], a[k])
        end
    end
end
return M = {m[i][j]}

（a）このアルゴリズムがBig-O（n ^ 3）比較を使用して行列Mを計算することを示します。
（b）このアルゴリズムがBig-Omega（n ^ 3）比較を使用して行列Mを計算することを示します。

この面とパート（a）を使用して、アルゴリズムがBig-theta（n ^ 3）比較を使用していると結論付けます。

4

2 に答える 2

5

パートAでは、操作数の上限を見つける必要がありますmin。

そうするために、上記のアルゴリズムの操作が次のアルゴリズムよりも少ないことは明らかです。 min

for i=1 to n
  for j=1 to n //bigger range then your algorithm
    for k=1 to n //bigger range then your algorithm
        (something with min)

上記には正確にn^3 minopsがあります。したがって、アルゴリズムでは、minopsよりも少なくなりn^3ます。

これから、次のように結論付けることができます#minOps <= 1 * n^3（n> 10ごとに、10は任意です）。 Big-Oの定義
により、これはアルゴリズムがO(n^3)

あなたはBを一人で理解できると言ったので、試してみましょう:)

ヒント：真ん中のループには、より多くの反復がありますfor j=i+1 to n/2

于 2012-10-14T15:21:57.403 に答える
0

外側のループの反復ごとに、内側の2つのネストされたループはn^2複雑になりますi == n。外側のループはのために実行されi = 1 to nます。したがって、全体的な複雑さは次のようなシリーズになります1^2 + 2^2 + 3^2 + 4^2 + ... ... ... + n^2。この合計値はn(n+1)(2n+1)/6です。この合計項の下位項を無視すると、最終的には次のようになります。O(n^3)

于 2012-10-14T15:40:18.137 に答える