Phân tích khấu hao cho một chuỗi các hoạt động được sử dụng để xác định thời gian chạy, thời gian trung bình theo yêu cầu của chuỗi. In không thể được coi là một phân tích trường hợp trung bình được thực hiện trên thuật toán vì nó không phải lúc nào cũng lấy trường hợp trung bình. Có những trường hợp xảy ra như một tình huống xấu nhất của phân tích. Vì vậy, phân tích khấu hao có thể được coi là phân tích trường hợp xấu nhất cho nhiều hoạt động trong một trình tự. Ở đây, chi phí thực hiện mỗi hoạt động khác nhau và đối với một số chi phí của nó rất cao. Vấn đề này là một cái nhìn chung bằng cách sử dụng bộ đếm nhị phân.
Hãy xem cách làm việc và triển khai trong ngôn ngữ lập trình c ++ để chúng ta hiểu rõ hơn về các khái niệm.
Bộ đếm nhị phân k-bit được thực hiện bằng cách sử dụng một mảng nhị phân có độ dài k mà ban đầu có giá trị bằng 0. Trên giá trị này, phép toán tăng dần được thực hiện nhiều lần. Dưới đây là cách mảng 8-bit nhị phân sẽ hoạt động trên hoạt động gia tăng được thực hiện trên nó.
Ban đầu, 00000000> 00000001> 00000010> 00000011> 00000100> 00000101> ....> 11111111.
Logic này là để kiểm tra sự xuất hiện của số 0 đầu tiên từ bit cuối cùng của số và lật nó thành 1 và tất cả các bit tuần tự theo sau nó thành 0.
Ví dụ
#include <iostream>
using namespace std;
int main(){
int number[] = {1,0,0,1,0,1,1,1};
int length = 8;
int i = length - 1;
while (number[i] == 1) {
number[i] = 0;
i--;
}
if (i >= 0)
str[i] = 1;
for(int i = 0 ; i<length ; i++)
cout<<number[i]<<" ";
} Đầu ra
1 0 0 1 0 0 0 0
Trong bài toán này, chi phí của mỗi hoạt động là không đổi và không phụ thuộc vào số lượng bit,
Ở đây, phân tích tiệm cận cho chi phí của một chuỗi là O (n).
Tổng số lần lật được thực hiện trong n thao tác là - n + n / 2 + n / 4 +… .. + n / k 2 k trong số lần lật.
Đây là một GP với HP ở mẫu số.
Tổng của lần lật
Tính tổng =n + n / 2 + n / 4 +… .. + n / k
2
Giờ đây, chi phí hoạt động được thơm hóa là O (n) / 2n =O (1)
Thứ tự là O (1) không tỷ lệ với n số bit trong số.