이진 카운터 상각 된 분석

Question

여러분이 이미 알고있는 것처럼 생각합니다. 배열의 모든 항목이 0에서 시작하고 각 단계에서 카운터를 1 씩 (0과 1을 바꿈으로써) 증가시킨 다음 k 증분에 대한 상각 된 비용은 O입니다. 케이).

그러나 배열이 n으로 시작하면 어떻게됩니까? 하지만 k (1)의 최대 수는 log (n)이기 때문에 k 증분의 복잡성은 이제 O (log (n) + k) 일 것입니다.

제안 사항?

미리 감사드립니다.

Answer 1

당신이 옳습니다. 이것을 증명할 수있는 방법은 여러 가지가 있습니다. 그 중 하나는 잠재적 인 기능입니다. This link (및 많은 다른 사람) 잠재적 인 방법을 설명합니다. 그러나 교과서는 일반적으로 잠재 함수의 초기 값을 0으로 요구합니다. 그렇지 않은 경우를 일반화합시다.

이진 카운터의 경우 카운터의 잠재적 기능은 1로 설정된 비트 수입니다. 증가 할 때 k1을 0으로, 1을 0으로 1을 사용합니다. k-1이다. 따라서이 증가분의 상각 된 시간 = ActualTime + (PotentialAfter-PotentialBefore) = k + 1- (k-1) = 2 (상수).

위키피디아 링크의 "상각 된 시간과 실제 시간 사이의 관계"섹션을보십시오. SumOfChangesToPotential 이후

TotalAmortizedTime = TotalActualTime + SumOfChangesToPotential 

는 FinalPotential-InitialPotential 같은지, 신축이다. 그래서 :

TotalAmortizedTime = TotalActualTime + FinalPotential-InitialPotential 

주는 :

TotalActualTime = TotalAmortizedTime - FinalPotential + InitialPotential <= TotalAmortizedTime + InitialPotential 

을 그래서, 당신이 말한대로, N으로 시작하는 K 단위의 순서에 대한 총 시간입니다 O를 (N + K 로그).