0 
if x:
    for i in range(a):
       for z in range(a):
          for k in range(z):
             for p in range(i):
                c = (i * z) + (k * p)
else:
    for i in range(a):
       for z in range(a):
          for k in range(z):
              c = (i * z) + (k * p)

これはO（n ^ 4）でしょうか？また、何回の掛け算が起こりますか？

編集：コードを更新しました。また、下限は有効な入力が強制する最大ステップ数をキャプチャするので、大きなオメガもn ^ 4ではないでしょうか？

4

2 に答える 2

0

次のコードは、すべての数値、、、がO（n）の場合にのみ、O（n 4 ）になります。azi

for i in range(a):
   for z in range(a):
      for k in range(z):
         for p in range(i):
            c = (i * z) + (k * p)

あなたが書いたように、私たちが知っているのは、そのコードブロックがO（a 2 zi）であるということだけです。同様に、発生する乗算の​​総数は2a2ziになります。また、、、、およびがすべてO（n）の場合、乗算の数はO（n a4 ）になります。zi

コードの2番目のブロックについて何を知りたいのかわかりません。

于 2012-04-08T06:35:09.770 に答える
0

はい、複雑さはまだO(n^4)です。簡単にするために、コードを再配置するための秘訣は次のとおりです。

for i in range(a):
   for p in range(i):
       f(i, p)

どこにf(i, p)ありますか

for z in range(a):
    for k in range(z):
        c = (i * z) + (k * p)

最初の部分では、最大次数までf(i, p)実行されています（合計のため、自分で計算してください）。同様に、の複雑さは再びに等しくなります。O(n^2/2)sum_i (i^2)f(i, p)f(i, p)O(n^2/2)

したがって、結果の順序は。になりO(n^4/4)ます。演算ごとに2つの乗算があるため、乗算の数は次のようになります。O(n^4/2)

于 2012-04-08T06:38:57.347 に答える