algorithm - 简单算法的大 O 表示法表示

Question

如何用 Big-O 表示法表示其复杂性？我有点困惑，因为第二个 for 循环根据外部循环的索引而变化。还是 O(n^2) 吗？还是不那么复杂？提前致谢

for (int k = 0; k<arr.length; k++){
      for (m = k; m<arr.length; m++){
           //do something
      }
}

Answer 1

您的估计来自级数公式：

因此，是O(n^2)。为什么你的案子是进展的？因为它是n + (n-1) + ... + 1您循环的总和。

Answer 2

如果将第二个循环的所有迭代相加，则得到 1+2+3+...+n，它等于 n(n+1)/2（n 是数组长度）。即 n^2/2 + n/2。您可能已经知道，大哦记法中的相关项是最大幂的一个，而系数不相关。所以，你的复杂度仍然是 O(n^2)。

Answer 3

那么运行时间是 n^2 循环的 cca 一半

• 但在大 O 表示法中，它仍然是 O(n^2)
• 因为任何恒定的时间/周期 - 操作都表示为 O(1)
• 所以 O((n^2)/2) -> O((n^2)/c) -> O(n^2)
• 非正式地有很多人使用 O((n^2)/2) 包括我自己的目的（它更直观和可比较）......更接近循环/运行时

希望能帮助到你