time-complexity - 以下算法的大 O 复杂度是多少？

Question

我需要帮助了解如何分解此功能，以便我知道如何回答所提出的问题？我知道增长的顺序，但仍然对如何在算法上阅读这个有一些疑问？

以下函数的大 O 复杂度是多少？

def complexity(n):
  k = 0
  for i in range(2, n):
    for j in range(n, 2*n):
      k= k+1

• (a) 复杂度1：O(n ³ )
• (b) 复杂度1：O(n ² )
• (c) 复杂度1：O(n)
• (d) 复杂度1：O(nlog _n )
• (e) 以上都不是

标签： time-complexitybig-o

Answer 1

如果考虑总和

您可以看到执行的步骤数正好是(n-2)*n.
因此，时间复杂度T(n) = O(n^2)。

实际例子：

>>> complexity(5)
15
>>> complexity(10)
80
>>> complexity(20)
360