Phương pháp đếm thao tác (Operation Counts Method) trong Thuật toán

Có nhiều phương pháp ước lượng chi phí thuật toán. Một trong số đó là đếm thao tác. Có thể ước lượng độ phức tạp thời gian bằng cách chọn một trong các thao tác khác nhau như cộng, trừ, v.v. Kiểm tra bao nhiêu thao tác được thực hiện. Thành công phụ thuộc vào khả năng xác định thao tác đóng góp lớn nhất cho độ phức tạp thời gian.

Giả sử có mảng kích thước n [0 đến n-1]. Thuật toán tìm chỉ mục phần tử lớn nhất. Ước lượng chi phí bằng cách đếm số phép so sánh giữa các cặp phần tử. Nhớ rằng chỉ chọn một thao tác. Trong thuật toán còn có thao tác khác như tăng biến lặp i, gán giá trị cho chỉ mục. Nhưng không xét trong trường hợp này.

Thuật toán

getMax(arr, n):
    index := 0
    max := arr[0]
    for i in range 1 to n - 1, do
        if arr[i] > max, then
            max := arr[i]
            index := i
        end if
    done
    return index

Chọn thao tác thực hiện nhiều nhất để ước lượng chi phí. Ví dụ bubble sort, đếm phép hoán đổi (swap). Phải nhớ khi nào swap tối đa để cho kết quả phân tích tệ nhất (worst-case).