PHÂN TÍCH TT CHÈN TRỰC TIẾP

void BubbleSort(int a[n])
{ int i,j,temp;
/*1*/ for(i= 0; i<=n-2; i++)
/*2*/ for(j=n-1; j>=i+1;j--)
/*3*/ if (a[j].key < a[j-1].key) {
/*4*/ temp=a[j-1];
/*5*/ a[j-1] = a[j];
/*6*/ a[j] = temp;
}
}
Đây là chương trình sử dụng các vòng lặp xác định. Toàn bộ chương trình chỉ gồm một lệnh lặp {1}, lồng trong lệnh {1} là lệnh lặp {2}, lồng trong lệnh {2} là lệnh {3} và lồng trong lệnh {3} là 3 lệnh nối tiếp nhau {4}, {5} và {6}.
Chúng ta sẽ tiến hành tính độ phức tạp theo thứ tự từ trong ra.
Trước hết, cả ba lệnh gán {4}, {5} và {6} đều tốn O(1) thời gian, việc so sánh a[j-1] > a[j] cũng tốn O(1) thời gian, do đó lệnh {3} tốn O(1) thời gian.
Vòng lặp {2} thực hiện (n-i) lần, mỗi lần O(1) do đó vòng lặp {2} tốn O((n-i).1) = O(n-i).
Vòng lặp {1} có i chạy từ 1 đến n-1 nên thời gian thực hiện của vòng lặp {1} và cũng là độ phức tạp của giải thuật là

n(n-1)/2=O(n2)