Phương pháp đếm hoạt động trong thuật toán

Có nhiều phương pháp khác nhau để ước tính chi phí của một số thuật toán. Một trong số chúng bằng cách sử dụng số hoạt động. Chúng ta có thể ước tính độ phức tạp về thời gian của một thuật toán bằng cách chọn một trong các phép toán khác nhau. Chúng giống như cộng, trừ, v.v. Chúng ta phải kiểm tra xem có bao nhiêu hoạt động trong số này được thực hiện. Sự thành công của phương pháp này phụ thuộc vào khả năng của chúng tôi trong việc xác định các hoạt động gây ra phần lớn sự phức tạp về thời gian.

Giả sử chúng ta có một mảng, kích thước n [0 đến n - 1]. Thuật toán của chúng tôi sẽ tìm chỉ số của phần tử lớn nhất. Chúng ta có thể ước tính chi phí bằng cách đếm số lượng thao tác so sánh được thực hiện giữa mỗi cặp phần tử của mảng. Chúng ta phải nhớ rằng, chúng ta sẽ chỉ chọn một thao tác. Trong thuật toán này, có thêm một số thao tác như tăng biến lặp i hoặc gán giá trị cho chỉ mục, v.v. Nhưng chúng không được xem 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úng tôi phải chọn những hoạt động được thực hiện trong khoảng thời gian tối đa để ước tính chi phí. Giả sử chúng ta có một thuật toán sắp xếp bong bóng và chúng ta đếm thao tác hoán đổi. Sau đó, chúng ta phải ghi nhớ rằng khi nào nó sẽ là tối đa. Điều đó sẽ cung cấp cho chúng tôi kết quả tối đa trong quá trình phân tích.