algorithm - 复杂度时间 O(n) 或 O(n(n+1)/2)

Question

循环 n 个项目(如数组)然后循环 (n-1) 然后循环 (n-2) 等等的算法的复杂性如何:

Loop(int[] array) {
  for (int i=0; i<array.Length; i++) {
     //do some thing

  }
}
Main() {
   Loop({1, 2, 3, 4}); 
   Loop({1, 2, 3}); 
   Loop({1, 2}); 
   Loop({1}); 
//What the complexity of this code.
}

前面程序的复杂度是多少？

Answer 1

假设你在循环中做的事情是O(1)，它的复杂度是O(n+(n-1)+(n-2)+... +1) = O(n(n+1)/2) = O(0.5n^2 + 0.5n) = O(n^2)

• 第一个=是算术级数和。
• 第二个=是由于开乘。
• 第三个 = 是因为给定 O() 中的多项式，您可以简单地将其替换为 x^highest_power