一个简单算法的Big-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你的循环的总和.