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ố lần so sánh phụ thuộc vị trí phần tử cần tìm; trong trường hợp xấu nhất phải duyệt theo kích thước n, vì vậy độ phức tạp là O(n). Bài thực hành hướng dẫn hai bước: phân tích các câu lệnh để tính tổng số phép tính cơ bản, sau đó lấy bậc tăng chủ đạo để xác định O-lớn.

Với sắp xếp chọn:

for i in range(n-1):
    for j in range(i+1, n):
        if A[j] < A[iMin]:
            iMin = j

Tổng số phép so sánh chứa tổng 1 + 2 + ... + (n-1). Nguồn đưa ra hàm thời gian đại diện:

T(n) = n² + 3n - 3

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