小编New*_*mer的帖子

嘿,有人可以帮我确定复杂性吗？我班上给出的一个例子是

泡泡排序

int main() {
   int a[10] = {10,9,8,7,6,5,4,3,2,1};
   int i,j,temp;

   for (j=0;j<10;j++) {
      for (i=0;i<9;i++) {
         if (a[i] > a[i+1]) {
            temp = a[i];
            a[i] = a[i+1];
            a[i+1] = temp;
         }
      }
   }
   for (i=0;i<10;i++) {
      printf("%d ",a[i]);
   }
}

其复杂度为O(n ^ 2),因为它有两个O(n)循环,因此O(n)x O(n).

并且他们说quicksort的复杂度为O(nlog(n))..为什么会这样？

是因为它围绕一个循环划分一个数字？

-谢谢