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

Question

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

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

Answer 1

您的估计来自progression公式:

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