ネストループ内の乗算数：Big O

Question

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）ですか？また、何回の乗算が起こるか？

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

Answer 1

はい、複雑さはまだO(n^4)です。物事をシンプルにするために、ここにコード

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)のために実行された

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

を再配置するためのトリックです和算sum_i (i^2)、自分で数学を行う）。同様に、f(i, p)はf(i, p)の複雑さを有し、これもまたO(n^2/2)に等しい。

したがって、合成された順序はO(n^4/4)です。各演算に2つの乗算があるので、乗算の回数はO(n^4/2)

Answer 2

次のコードは、O（N ）すべての数字aであれば、zなり、そしてiはO（N）でした。

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（ ZI）であるということです。同様に、発生する乗算の​​総数は、2a ziとなります。また、a,z、およびiがすべてO（n）である場合、乗算の回数はO（n ）となります。

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