这段代码是 O(n) 还是 O(n²)？（Python 代码）

Question

我们的教授给了我们这个代码作为大 O 符号 O(n) 的一个例子。但我想知道为什么。在我看来，这段代码是 O(n²)。我希望你能帮助我。

def g(n):

     x = n

     y = 1

     while x > 0:

          x = x - 1

          y = y + n

     while y > 0:

          y = y - 1

     return True

当我在循环中有一个循环时，我认为代码在 O(n²) 中。这段代码显示了两个单独的循环，所以它应该是 O(2n)，但我可以忽略常量，我得到了 O(n)。如果我错了，请纠正我。

谢谢你的帮助！

Answer 1

第一个循环是 O(N)。它运行的次数与 n 的大小成正比。第二个循环运行的次数与 y 的大小成正比。由于 y 在循环开始时等于 n**2，所以它是 O(N^2)。由于该函数包含一个 O(N) 循环和一个 O(N^2) 循环，因此该函数总共为 O(N^2)。

Answer 2

def g(n):     x = n           # x = n     y = 1     while x > 0:              x = x - 1  # loop through x times (since x=n, n times)           y = y + n  # in the end, y = (1 + n) + ((1+n) + n) + (((1+n) + n) + n) ... = n + n*n     while y > 0:    # loops n + n^2 number of times          y = y - 1     return True如您所见，这是因为 y 的值最终为 n + n^2，所以 O(n^2) 是时间复杂度。

Answer 3

你的代码的复杂度是O(n^2)因为y在第一个循环中总是以 n * n 结束，这将 n 添加到yn 次，所以第二个循环将迭代 n * n 次。