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

Question

我的印象是，要找到嵌套 for 循环的大 O，需要将每个 for 循环的大 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 .最里面的循环以类似的方式上升。我们注意到的是所有这些都是常数!调用打印语句的次数实际上根本没有变化。当算法在恒定时间内运行时，我们将其表示为 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)

在这个例子中，打印语句被称为 2n^2 + 3n次。对于第一组循环， n外循环的次数， n内循环的时间，然后是 2内圈内的次数。对于第二组， n循环次数和 3每次迭代次数。首先我们去掉常量，留下 n^2 + n ，从长远来看，现在什么最重要？当 n是 1 ，两者都无关紧要。但更大的 n得到，相差越大， n^2增长速度远快于 n - 所以这个函数有复杂性 O(n^2) .