algorithm - 嵌套循环中的乘法数：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) 吗？另外，会发生多少次乘法？

编辑：更新了代码。另外，由于下限捕获了有效输入将强制执行的最大步数，所以大欧米茄不也是 n^4 吗？

Answer 1

如果所有数字、和均为 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 ² zi)。同样，将发生的乘法总数为：2a ² zi。并且，再次，如果a、z和i都是 O(n)，则乘法数将为 O(n ⁴ )。

我不确定你想知道关于第二个代码块的什么。

Answer 2

是的，复杂性仍然是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)。并且每个操作有两次乘法，所以乘法的次数是O(n^4/2)