상각 분석 작업 시퀀스의 경우 실행 시간, 즉 시퀀스에 필요한 평균 시간을 결정하는 데 사용됩니다. In은 항상 평균 사례 시나리오를 취하지 않기 때문에 알고리즘에서 수행된 평균 사례 분석으로 취급될 수 없습니다. 분석의 최악의 시나리오로 발생하는 경우가 있습니다. 따라서 상각 분석은 시퀀스의 여러 작업에 대한 최악의 경우 분석으로 처리될 수 있습니다. 여기에서 각 작업을 수행하는 비용은 서로 다르고 일부는 높습니다. 이 문제는 바이너리 카운터를 사용하는 일반적인 보기입니다.
개념을 명확하게 하기 위해 C++ 프로그래밍 언어에서 작동 및 구현을 살펴보겠습니다.
k 비트 이진 카운터는 초기 값이 0인 길이 k의 이진 배열을 사용하여 구현됩니다. 이 값에서 증분 연산이 여러 번 수행됩니다. 다음은 바이너리 8비트 배열이 수행된 증가 연산에서 어떻게 작동하는지입니다.
처음에는 00000000> 00000001> 00000010> 00000011> 00000100> 00000101>....> 11111111.
이 논리는 숫자의 마지막 비트부터 처음 0이 발생하는지 확인하여 1로 반전하고 그 뒤에 오는 모든 비트를 순차적으로 0으로 반전시키는 것입니다.
예시
#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]<<" ";
} 출력
1 0 0 1 0 0 0 0
이 문제에서 각 연산의 비용은 일정하며 비트 수에 의존하지 않습니다.
여기서 시퀀스 비용에 대한 점근적 분석은 O(n)입니다.
n개의 연산으로 수행된 총 뒤집기 횟수는 − n + n/2 + n/4 + ….. + n/k 2 입니다. k는 뒤집기 횟수입니다.
분모에 HP가 있는 GP입니다.
뒤집기의 합
합계 =n + n/2 + n/4 + ….. + n/k
2
이제 방향족화된 운영 비용은 O(n) / 2n =O(1)입니다.
순서는 O(1)이며 숫자의 비트 수 n에 비례하지 않습니다.