Phương pháp đếm bước (Step Count Method) là một phương pháp phân tích thuật toán. Đếm số lần mỗi lệnh thực hiện, từ đó tìm độ phức tạp.
Ví dụ thuật toán tìm kiếm tuần tự (sequential search). Giả sử mỗi lệnh tốn c₁, c₂,... thời gian:
| Thuật toán | Số lần thực thi | Chi phí |
|---|---|---|
|
seqSearch(arr, n, key) i := 0 while i < n, do if arr[i] = key then break end if done return i |
1 n+1 n 0/1 1 |
c₁ c₂ c₃ c₄ c₅ |
Tổng chi phí trường hợp xấu nhất:
Cost = c₁ + (n+1)c₂ + nc₃ + c₄ + c₅
Cost = n(c₂+c₃) + (c₁+c₄+c₅)
Cost = n(c₂+c₃) + C (với C = c₁+c₄+c₅ hằng số)
Đây là phương trình đường thẳng y = mx + b. Do đó hàm là tuyến tính. Độ phức tạp O(n).