乘法嵌套循环数：大O [英] Number of Multiplications in nested loops: Big O

问题描述

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）？此外，有多少次乘法会出现？

Would this be O(n^4)? Also, how many multiplications would occur?

编辑：更新了code。而且，由于下限捕获的步骤的有效输入将迫使最大数目，也不会大的ω为n ^ 4以及

updated the code. Also, since the lower bound captures the max number of steps a valid input will force, wouldn't big omega be n^4 as well?

推荐答案

是的，复杂度仍然为O（n ^ 4）。为了使事情变得简单，这里有个技巧重新安排code

Yes, the complexity is still O(n^4). To make things simple, here is the trick to rearrange your code

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）。

In the first part, f(i, p) has been executed for O(n^2/2) up to the largest order (because of the summation sum_i (i^2), do the math yourself). Similarly, the f(i, p) has the complexity of f(i, p) which is again equal to O(n^2/2).

因此​​，合并产生的顺序是为O（n ^ 4/4）。并有两个乘法每次操作，所以乘数为为O（n ^ 4/2）

So the combined resulting order is O(n^4/4). and there is two multiplications for each operation, so number of multiplication is O(n^4/2)

这篇关于乘法嵌套循环数：大O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！