Thực hành xác định độ phức tạp thời gian thuật toán

Hiểu bài

Với tìm kiếm tuần tự, số phép toán phụ thuộc vị trí phần tử cần tìm; trường hợp xấu nhất phải xét toàn bộ n phần tử, nên độ phức tạp là O(n). Với sắp xếp chọn, vòng ngoài chạy n - 1 lần và vòng trong xét phần còn lại của dãy. SGK tính:

T(n) = 1 + 4(n - 1) + 2∑(k, k=1..n-1)
     = 1 + 4(n - 1) + n(n - 1)
     = n² + 3n - 3

Do thành phần n² tăng nhanh nhất, thuật toán sắp xếp chọn có độ phức tạp thời gian O(n²).