如何计算嵌套循环的时间复杂度（Big O）

Question

我认为对于嵌套的for循环，找到它们的大O表示法，需要将每个for循环的大O表示法与下一个for循环的相乘。那么以下代码的大O表示法是：

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

be O(5n)吗？如果是这样，那么对于以下的big O是多少：

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

我应该翻译成O(n^3)，因为它嵌套了3次。你是不是被搞糊涂了？

- Malaikatu Kargbo

---

O(5n) 是 O(n)，所以第一个例子就是 O(n)。第二个例子归结为只是一个数字，因此它是 O(1)。 - inspectorG4dget

Answer 1

这是一个简化版，但希望它能清楚地表达Big-O的含义：

Big-O涉及问题“我的代码执行了多少次操作？”，用代数回答该问题，然后问“在长期运行中哪个项最重要？”。

对于第一个例子-打印语句被调用的次数是5n次。 外部循环的次数是n次，内部循环的次数是5次。 长期运行中，什么最重要？长期运行中只有n最重要，因为5的值永远不会改变！ 因此，总体的Big-O复杂度是O（n）。

对于第二个示例-打印语句被调用的次数非常大，但却是一个恒定的数字。外部循环运行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)。

- jambrothers

---

太好了。这正是我所期望的答案。 - John Kugelman

Answer 2

你对第二个例子的O(n^3)是正确的。你可以像这样计算大O：

任何数量的嵌套循环都会将1的幂次方加到n上。所以，如果我们有三个嵌套循环，大O将是O(n^3)。对于任意数量的循环，大O是O(n^(循环数))。一个循环只是O(n)。任何n的单项式，例如O(5n)，都只是O(n)。

- Ajax1234

Answer 3

您误解了O(n)的含义。这在一开始很难理解，所以不理解没有关系。
O(n)的意思是“最多以n的速度增长”。它有一个严格的数学定义，但基本上可以简化为以下内容。
如果f和g都是函数，f=O(g)表示您可以选择一些常数C，在像n这样的大输入上，f(n)

- E.D.

---

这并没有回答第二个例子。 - John Kugelman