Đánh giá độ phức tạp của hàm Selection Sort

Trong hàm Selection Sort, có gọi thủ tục Swap ta dễ thấy rằng hàm Swap có 3lệnh gán nên thời gian thực hiện là O(1).
Trong Selection Sort lệnh gọi Swap nên chỉ tốn O(1), dòng for thứ 2 thực hiện n-i lần, mỗi lần thực hiện tốn O(1) nên tốn O (n-i) và đây cũng là độ phức tạp của hàm:
T(n) =∑_(i=1)^(n-1)▒(n-i) = (n(n-1))/2 = O(n^2)

Bài tập nhóm hai:

Câu lệnh (4) thực hiện O(1) câu lệnh (3) thực hiện O(1), cả hai câu lệnh thực hiện O(1+1)=O(1)
Câu lệnh (2) thực hiện 1 lần
Câu lệnh (1) thực hiện n-1 lần
T(n)=∑i=1+2+…..+n-1=[n(n-1)]/2
Vậy độ phức tạp của thuật toán là O(n^2)

duongvandeoit1k10 đã viết:

Code:

void SelectionSort(int A[],int n) {
    int min;
    for(int i=0; i<n-1; i++) {
          min = i;
          for(int j=i+1; j<n; j++)
          if(A[min]>A[j])
          min = j;
          if(min != i)
                Swap(A[i],A[min]);
          }
}

Trong hàm Selection Sort, có gọi thủ tục Swap ta dễ thấy rằng hàm Swap có 3lệnh gán nên thời gian thực hiện là O(1).
Trong Selection Sort lệnh gọi Swap nên chỉ tốn O(1), dòng for thứ 2 thực hiện n-i lần, mỗi lần thực hiện tốn O(1) nên tốn O (n-i) và đây cũng là độ phức tạp của hàm:
T(n) =∑_(i=1)^(n-1)▒(n-i) = (n(n-1))/2 = O(n^2)

===============================================
Thầy ơi sao thầy hông cho nhận xét bài làm của em vây? Em làm thế có đúng không ạ?

duongvandeoit1k10 đã viết:

Code:

void SelectionSort(int A[],int n) {
    int min;
    for(int i=0; i<n-1; i++) {
          min = i;
          for(int j=i+1; j<n; j++)
          if(A[min]>A[j])
          min = j;
          if(min != i)
                Swap(A[i],A[min]);
          }
}

Em làm bài này vầy nè thầy xem có đúng không thầy
lenh Swap= O(1)lồng trong lệnh if ma if cũng O(1) nên 2 câu lệnh bằng O(1).
if va min cung bang O(1)
for thi bằng O(n-i-1)
lồng trong dòng for cua i ma for cua i = O(n-1)
T(n)=O((n-i-1)*(n-1))=O(n^2-in-2n+i+1). Mà i đi đến n-2 nên T(n)=O(n^2-n(n-2)-2n+n-2+1)=O(n-1)
Vậy đúng không thầy.