如何计算嵌套for循环的Big O

Question

我的印象是，要找到嵌套的for循环的大O，则将每个forloop的大O与下一个for循环相乘。大O是否适合：

    for i in range(n):
         for j in range(5):
              print(i*j)

是O（5n）吗？如果是的话，大O将：

 for i in range(12345):
      for j in range(i**i**i)
           for y in range (j*i):
                print(i,j,y)

是O(12345*(i**i**i)*(j*i)？还是O(n^3)因为嵌套了3次？我很混乱

Answer 1

这有点简化了，但是希望可以理解Big-O的含义：

Big-O的问题是“我的代码可以执行多少次？”，用代数回答，然后问“从长远来看，哪个术语最重要？”

对于第一个示例- print调用语句的次数为5n次。n外循环中的时间5乘以内循环中的时间。从长远来看，最重要的是什么？从长远来看，只有n重要，因为5永不改变的价值！因此，总体来说，Big-O的复杂度为O(n)。

对于第二个示例-调用print语句的次数非常大，但是是恒定的。外循环运行12345一次，内循环运行一次，然后运行16几次，然后7625597484987一直到12345^12345^12345。最内层的循环以类似的方式上升。我们注意到的是所有这些都是常量！实际上，调用print语句的次数根本没有变化。当算法在恒定时间内运行时，我们将其表示为O(1)。从概念上讲，这是类似于上面的例子-就像5n / 5 == n，12345 / 12345 == 1。

您选择的两个示例仅涉及去除常数因子（我们在Big-O中始终这样做，它们永远不会改变！）。另一个示例是：

def more_terms(n):
  for i in range(n):
    for j in range(n):
      print(n)
      print(n)
  for k in range(n):
    print(n)
    print(n)
    print(n)

对于此示例，print语句称为2n^2 + 3n次。对于第一组循环，n外部循环的n时间，内部循环的时间，然后2是内部折叠的时间。对于第二组，n循环3次数和每次迭代次数。首先，我们去除常数，然后离开n^2 + n，从长远来看，现在重要的是什么？什么时候n是1，什么都不重要。但是，n获取越大，差异越大，n^2增长快得多n-因此该函数具有复杂性O(n^2)。

Answer 2

对于第二个例子，您关于 O(n^3) 的说法是正确的。你可以这样计算大O：

任意数量的嵌套循环都会增加 1 到 n 的额外幂。因此，如果我们有三个嵌套循环，那么大 O 将为 O(n^3)。对于任意数量的循环，大 O 是 O(n^(循环数量))。一个循环的时间复杂度仅为 O(n)。任何 n 的单项式，例如 O(5n)，都是 O(n)。