取舍排序时间复杂度计算浅析

选择排序时间复杂度计算浅析
选择排序时间复杂度计算浅析：
代码：

void select_sort(int a[], int n) {   for (i = 0; i < n - 1; ++i) {      j = i;      for (k = i + 1; k < n; ++k) {         if (a[k] < a[j]) j = k;         if (j != i) a[j] <--> a[i];      }   }} // select_sort

上述程序的原操作有赋值、比较及交换，显然基本操作应该取比较。总的比较次数显然是：(n-1)+(n-2)+(n-3)+...+1这是一个等差数列之和，要算出求和公式的话可以这样：

(n-1)+(n-2)+(n-3)+......+3+2+1=Sn
1+2+3+......+(n-3)+(n-2)+(n-1)=Sn

上边两个式子加起来2Sn=n+n+n+......+n+n+n(一共n-1个n)所以得出Sn=n(n-1)/2，
Sn=n^2-n/2和n^2成正比，因此选择排序的时间复杂度为O(n^2)。

查看更多 下一篇